Equation (1) —
ProvedOnlineStochMatching.TSM.eq_1bipartite-matchingmax-flowonline-algorithmsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a finite bipartite graph, the edge set of an integral maximum flow of the boosted flow graph, and blue/red a TSM colouring of . Write , , , for the advertisers incident to one blue and one red edge, to two blue edges, to only a blue edge, and to only a red edge. Then
The identity says that every edge of is counted at its advertiser, and that no advertiser carries two red edges. It converts the bound on OPT, which is in terms of , into the advertiser classes in which ALG is bounded.
Preamble
import Mathlib import Definitions.Def_OnlineStochMatching_TSM_Coloring
Formal statement
namespace OnlineStochMatching.TSM
/-- **Equation (1)** (Feldman, Mehta, Mirrokni, Muthukrishnan, *Online Stochastic Matching: Beating
1-1/e*, arXiv:0905.4100v1, §4.2.2, p. 7): for a maximum flow edge set `E_f` and a TSM colouring
`(blue, red)` of it,
`|E_f| = 2|A_BR| + 2|A_BB| + |A_B| + |A_R|`,
where `A_BR`, `A_BB`, `A_B`, `A_R` are the advertisers incident to one blue and one red edge, to
two blue edges, to only a blue edge, and to only a red edge. -/
theorem eq_1 {A I : Type} [Fintype A] [DecidableEq A] [Fintype I] [DecidableEq I]
(E F blue red : Finset (A × I)) (hF : IsMaxFlowSet E F) (hcol : IsTSMColoring F blue red) :
F.card = 2 * (adsBR blue red).card + 2 * (adsBB blue red).card + (adsB blue red).card +
(adsR blue red).card := by sorry
end OnlineStochMatching.TSM
Source
Feldman, Mehta, Mirrokni, Muthukrishnan, Online Stochastic Matching: Beating 1-1/e, arXiv:0905.4100v1, p. 7, Section 4.2.2, equation (1)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.