Lemma C.7 — k-way delay bound
OpenMatchingDelays.Linear.Supplement.kway_delay_boundFix an integer and an input of requests with , located at points of an arbitrary metric space and arriving at times . Write , and . Let be any execution of the k-way Delayed Best-Effort Matching algorithm of §C.3 with any tie-breaking: an active component grows its dual at rate when and is frozen otherwise; two active components merge when a crossing pairwise constraint becomes tight; any unmatched requests of one active component are grouped once . Quantities at time refer to the state after all arrivals, merges and group formations at ; for ; is the set of arrived ungrouped requests and .
Let be the time at which is grouped, and the final dual. Then
The bound does not involve the group connection cost, so it can be reused for other connection objectives.
Differences from the source:
- encoding: requests labeled [n] in continuous real time → arrival-ranked Fin n input, batched simultaneous arrivals, and natural-number microsteps with exact continuous interpolation; time-indexed objects are read from the completed event state at t; reason: relabeling preserves all inputs and ties; microsteps do not discretize time, and they order arrivals, merges and matches at one instant exactly as the source does
import Mathlib import Definitions.Def_MatchingDelays_Linear_Supplement_KWay set_option autoImplicit false open scoped BigOperators open Classical noncomputable section
namespace MatchingDelays.Linear.Supplement
variable {n : ℕ} {X : Type*} [MetricSpace X]
/-- Lemma C.7 (printed 32 / PDF 33): `delay ≤ 64(k−1)/ln 2 · (1 + 3 ln n) · dual`. -/
theorem kway_delay_bound (k : ℕ) (I : Instance n X) (hk : ValidKSize k n) (R : KRun) (hR : IsKExecution k I R) :
kDelay I R ≤ (64 * ((k : ℝ) - 1) / Real.log 2) * (1 + 3 * Real.log (n : ℝ)) * kFinalDual R := by sorry
end MatchingDelays.Linear.Supplement