Lemma 5.7 — optimal paths of two free requests coincide or share no edge; interiors have arrived
OpenBipartiteVRM.Competitive.Supplement.lemma_5_7competitive-analysismatching-with-delaysnon-bipartite-matchingonline-algorithmsp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix , any tie rule, an MPMD input with , any minimum-cost perfect matching on under , and a time . Let and be distinct free requests at time .
- If is the terminal request of , then and have the same edges.
- Otherwise and share no edge.
- Every interior vertex of the optimal path of a free request at time has arrived by .
This governs the charging scheme of §5.4: at most two requests, the two ends of one optimal path, charge an edge of at the same time.
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: the optimal path P_u(t), the component of M_t △ M containing u, its terminal request and interior vertices → the vertex list optimalWalk of M_t = stateAt t and M* from u, its last element and its dropLast.tail; same edges as equality of edge sets; reason: the walk alternately follows the M*-edge and the M_t-edge and so traverses that component; the fuel n + 1 never truncates it
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.7, p. 17: same edges or no shared edge, and arrived interiors. -/
theorem lemma_5_7 {n : ℕ} {X : Type*} [MetricSpace X] (I : Instance n X) (hn : Even n)
(γ : ℝ) (hγ : 1 < γ) (tie : TieRule) (Mstar : Matching) (hMstar : IsOptimal I Mstar)
(t : ℝ) :
(∀ u ∈ freeAt I γ tie t, ∀ w ∈ freeAt I γ tie t, u ≠ w →
((optimalPath I γ tie Mstar t u).getLast? = some w →
pathEdges (optimalPath I γ tie Mstar t u) =
pathEdges (optimalPath I γ tie Mstar t w)) ∧
((optimalPath I γ tie Mstar t u).getLast? ≠ some w →
Disjoint (pathEdges (optimalPath I γ tie Mstar t u))
(pathEdges (optimalPath I γ tie Mstar t w)))) ∧
(∀ u ∈ freeAt I γ tie t, ∀ z ∈ (optimalPath I γ tie Mstar t u).dropLast.tail,
MatchingDelays.Linear.arrival I z ≤ t) := by sorry
end BipartiteVRM.Competitive.Supplement
Source
Tung-Wei Kuo, STOC 2027 submission #528 (October 2026), p. 17, Lemma 5.7; definition of P*_u(t), p. 17