Lemma 5.4 — edgewise switching costs before and after a symmetric difference
OpenBipartiteVRM.Competitive.Supplement.lemma_5_4competitive-analysismatching-with-delaysnon-bipartite-matchingonline-algorithmsp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let and be matchings and . With for and otherwise:
- every edge satisfies ;
- every edge satisfies
These identities compare γ-net-costs with respect to the offline matchings before and after an augmentation, edge by edge, in the induction step of Lemma 5.5.
Differences from the source:
- generalization: matchings M, M′, D the TA distance, fixed γ > 1 → matchings M, M′ on natural labels, any edge function D : Edge → ℝ and any real γ; reason: both identities are case checks on membership and hold for every D and γ; the source's D 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.4, p. 16, both parts. -/
theorem lemma_5_4 (D : Edge → ℝ) (γ : ℝ) (M M' : Matching)
(hM : IsMatching M) (hM' : IsMatching M') :
(∀ e, e ∉ symmD M M' → switchCost D γ M' e = switchCost D γ M e) ∧
(∀ e ∈ symmD M M', switchCost D γ M e + switchCost D γ M' e = (γ - 1) * D e) := by sorry
end BipartiteVRM.Competitive.Supplement
Source
Tung-Wei Kuo, STOC 2027 submission #528 (October 2026), p. 16, Lemma 5.4 (a) and (b)