Lemma 5.2 — weight change in equals the γ-net-cost of
OpenBipartiteVRM.Competitive.Supplement.lemma_5_2competitive-analysismatching-with-delaysnon-bipartite-matchingonline-algorithmsp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let be a matching, let be vertices unsaturated by , and let be the complete graph on the vertices saturated by together with and , weighted by for and otherwise. Every perfect matching of satisfies
This identity converts the minimum-weight perfect matching computation of Step 1 into a statement about γ-net-costs of ; it is used in Lemmas 5.3 and 5.5.
Differences from the source:
- generalization: M the offline matching at some state of non-bipartite VRM, u, v free requests, D the TA distance, fixed γ > 1 → any matching M on natural labels, any distinct M-unsaturated labels u, v, any edge function D : Edge → ℝ and any real γ; reason: the identity is an algebraic fact about finite edge sums and holds for every such M, D and γ; the source's state, requests, distance and γ are a special case
Preamble
import Definitions.Def_BipartiteVRM_Competitive_Supplement_Paths set_option autoImplicit false
Formal statement
namespace BipartiteVRM.Competitive.Supplement
open MatchingDelays.Linear (Instance Edge)
/-- Lemma 5.2, p. 15. -/
theorem lemma_5_2 (D : Edge → ℝ) (γ : ℝ) (M : Matching) (hM : IsMatching M)
(u v : ℕ) (huv : u ≠ v) (hu : ¬ saturated M u) (hv : ¬ saturated M v)
(N : Matching) (hN : IsPerfectOn (pairVertices M u v) N) :
weight D γ M N - weight D γ M M = netCost D γ M (symmD N M) := by sorry
end BipartiteVRM.Competitive.Supplement
Source
Tung-Wei Kuo, STOC 2027 submission #528 (October 2026), p. 15, Lemma 5.2