§4.1 Tightness — complete bipartite family
ProvedOnlineStochMatching.SuggestedMatching.tightnessbipartite-matchingoccupancyonline-algorithmsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
For every , take the complete bipartite graph with advertisers and impression types, each with . For every maximum expected-instance matching and every valid labelling, the hindsight optimum is in every scenario, while
This is the exact finite- expectation underlying the paper's statement that the factor is tight even in expectation. Each maximum matching is perfect in this family.
Preamble
import Definitions.Def_OnlineStochMatching_SuggestedMatching_Algorithm
Formal statement
namespace OnlineStochMatching.SuggestedMatching
/-- The exact expectation and optimum for the complete-graph family in Section 4.1. -/
theorem tightness :
∀ (n : ℕ) (hn : 0 < n),
let inst := completeInstance n hn
∀ (M : Finset (Fin n × Fin n)) (hM : IsMaxBMatching inst M)
(label : inst.Copy → Option (Fin n)) (hlabel : IsLabelling inst M label),
(∀ ω : Fin inst.n → inst.Copy, optimum inst ω = n) ∧
expectedAlgorithm inst label =
(n : ℝ) * (1 - (1 - 1 / (n : ℝ)) ^ 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, Tightness of the Analysis
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.