Lemma 5.8 — both optimal-path age bounds in the non-bipartite case
OpenBipartiteVRM.Competitive.Supplement.lemma_5_8competitive-analysismatching-with-delaysnon-bipartite-matchingonline-algorithmsp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix , any tie rule, an MPMD input with and any minimum-cost perfect matching on under . Let be a stable time and a free request at such that the terminal request of has arrived by , and let . Then
where .
These bounds make the Case 2 charge rates well defined and bound how long an edge of can be charged.
Differences from the source:
- encoding: a finite request set R with |R| = 2m in any metric space, locations and arrival times a_v ≥ 0 that may coincide → the published MatchingDelays.Linear.Instance n X (labels 0..n−1 in nondecreasing arrival order, any MetricSpace X) with Even n, m = n/2; reason: every finite input can be relabeled in arrival order (simultaneous arrivals in any order); labels give the algorithm no future data, and repeated locations and arrival times are allowed
- encoding: an arbitrary but fixed rule for ties among simultaneous events and among the choices of N_uv and v in Steps 1 and 2 → every TieRule, a View-and-history selector over the nonempty finite option sets; reason: the rule sees only received data and its own history; every statement quantifies over all such rules
- encoding: a stable time t (no request arrives and no augmentation is performed at t) → 0 ≤ t, no arrival at t and no output pair with time t; reason: for t < 0 there is no free request, so the condition 0 ≤ t excludes only vacuous cases
- encoding: the optimal path P_u(t), its terminal request and D = D(P* ∩ M*) → the vertex list optimalWalk from u, its last element, and the sum of TA distances over its edges in M*; reason: the walk traverses the component of M_t △ M* containing u
Preamble
import Definitions.Def_BipartiteVRM_Competitive_Supplement_Specifications set_option autoImplicit false
Formal statement
namespace BipartiteVRM.Competitive.Supplement
open MatchingDelays.Linear (Instance Edge)
/-- Lemma 5.8, p. 18: both bounds, the second at every vertex of P*. -/
theorem lemma_5_8 {n : ℕ} {X : Type*} [MetricSpace X] (I : Instance n X) (hn : Even n)
(γ : ℝ) (hγ : 1 < γ) (tie : TieRule) (Mstar : Matching) (hMstar : IsOptimal I Mstar)
(t : ℝ) (ht : stable I γ tie t) (u : ℕ) (hu : u ∈ freeAt I γ tie t)
(hterm : ∃ v, (optimalPath I γ tie Mstar t u).getLast? = some v ∧
MatchingDelays.Linear.arrival I v ≤ t) :
age I u t ≤ optimalLength I γ tie Mstar t u ∧
∀ z ∈ optimalPath I γ tie Mstar t u,
age I z t / (γ + 1) ≤ optimalLength I γ tie Mstar t u := by sorry
end BipartiteVRM.Competitive.Supplement
Source
Tung-Wei Kuo, STOC 2027 submission #528 (October 2026), p. 18, Lemma 5.8