§4.1 Bounding OPT — concentration of the hindsight optimum
ProvedOnlineStochMatching.SuggestedMatching.opt_boundbipartite-matchingconcentrationonline-algorithmsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
For any maximum integral expected-instance matching , let be its covered advertisers. For every , there are constants and independent of the instance and such that, whenever ,
The random optimum is the maximum matching of the arrival-by-arrival realization graph. The paper writes the failure probability as ; the formal statement gives its uniform quantifiers.
Preamble
import Definitions.Def_OnlineStochMatching_SuggestedMatching_Algorithm import Definitions.Def_OnlineStochMatching_SuggestedMatching_Cut
Formal statement
namespace OnlineStochMatching.SuggestedMatching
/-- Section 4.1's high-probability bound on the hindsight optimum. -/
theorem opt_bound :
∀ ε : ℝ, 0 < ε → ∃ δ : ℝ, 0 < δ ∧ ∃ N : ℕ,
∀ (A I : Type) [Fintype A] [Fintype I]
(inst : Instance A I) (hn : N ≤ inst.n)
(M : Finset (A × I)) (hM : IsMaxBMatching inst M),
runProbability inst (fun ω =>
(optimum inst ω : ℝ) ≤ (coveredAds M).card + ε * (inst.n : ℝ)) ≥
1 - Real.exp (-δ * (inst.n : ℝ)) := by sorry
end OnlineStochMatching.SuggestedMatching
Source
Feldman, Mehta, Mirrokni, Muthukrishnan, Online Stochastic Matching: Beating 1-1/e, arXiv:0905.4100v1, p. 6, §4.1, Bounding OPT
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.