§4.1 Bounding OPT — canonical cut identity
ProvedOnlineStochMatching.SuggestedMatching.cut_identitybipartite-matchingmax-flowp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1stochastic-matching
For any maximum integral expected-instance matching , let be the advertiser and type vertices reachable from the source in its residual network, and let . No edge of the original graph joins to a type outside , and
The identity equates the size of the selected integral flow with the capacity of its canonical minimum cut. It supports the scenario-wise bound on hindsight optimum.
Preamble
import Definitions.Def_OnlineStochMatching_SuggestedMatching_Cut import Definitions.Def_OnlineStochMatching_SuggestedMatching_Algorithm
Formal statement
namespace OnlineStochMatching.SuggestedMatching
/-- Section 4.1's canonical cut has no advertiser-to-type crossing edge,
and its capacity equals the maximum integral flow. -/
theorem cut_identity (A I : Type) [Fintype A] [Fintype I]
(inst : Instance A I) (M : Finset (A × I)) (hM : IsMaxBMatching inst M) :
(∀ a i, (a, i) ∈ inst.E → adInSourceSide inst M a → typeInSourceSide inst M i) ∧
(coveredAds M).card =
(adsInSinkSide inst M).card +
∑ i ∈ typesInSourceSide inst M, inst.e i := by sorry
end OnlineStochMatching.SuggestedMatching
Source
Feldman, Mehta, Mirrokni, Muthukrishnan, Online Stochastic Matching: Beating 1-1/e, arXiv:0905.4100v1, p. 5, §4.1, Bounding OPT, cut identity
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.