Theorem 3, p. 7 — Randomized-Batching with Depth-k Greedy is 1/d-competitive for Online-(k, d)-Max-Matching
ProvedHyperMatchDelay.Batching.theorem_3Let be a shareability hypergraph with parameters , , : vertices arrive one per time step, each hyperedge has diameter less than , at most vertices and non-negative weight. Run Randomized-Batching (Algorithm 1) with Depth-k Greedy (Algorithm 2) as the offline subroutine, where Greedy breaks weight ties in an arbitrary but fixed way. Draw the shift uniformly from and let be the output. Then:
- for every shift , is a matching of and every edge of lies inside a single batch window , so it can be committed online after all its vertices arrive and before any of them leaves;
- for every matching of ,
Taking to be a maximum weight matching shows that the algorithm is -competitive for Online-(k, d)-Max-Matching, the best possible ratio for by Theorem 1 of the paper, and it is achieved by a polynomial-time algorithm for fixed .
Formalization Note Only the competitive-ratio clause of Theorem 3 is formalized; the running-time clause is not. The comparison against every matching is equivalent to comparison against a maximum weight matching . Ties in Greedy are an ordering oracle and the statement holds for every weight-sorted oracle. Hyperedges are assumed non-empty.
import Mathlib import Definitions.Def_HyperMatchDelay_Batching_Model
namespace HyperMatchDelay.Batching
/-- Theorem 3, p. 7 (competitive clause; proof Appendix B.3, pp. 17–20): Randomized-Batching
using Depth-k Greedy as a subroutine is `1/d`-competitive for Online-(k, d)-Max-Matching.
For every shift `z < d` the output `M_z` is a matching of `E` whose every edge lies inside one
window (online feasibility), and its expected weight over a uniform shift
`Z ∈ {0, …, d - 1}` is at least `w(M̃)/d` for every matching `M̃` of `E`. -/
theorem theorem_3 (n d k : ℕ) (hd : 1 ≤ d) (hk : 1 ≤ k) (E : Finset (Finset ℕ))
(w : Finset ℕ → ℝ) (hE : IsShareability n d k E w)
(σ : Finset (Finset ℕ) → List (Finset ℕ)) (hσ : IsSortedOrder w σ) :
(∀ z < d, IsMatching E (randomizedBatching σ w n d k E z) ∧
∀ e ∈ randomizedBatching σ w n d k E z, ∃ i ∈ batchIndices n d, e ⊆ window n d z i) ∧
∀ Mt : Finset (Finset ℕ), IsMatching E Mt →
weight w Mt / d ≤
(1 / (d : ℝ)) * ∑ z ∈ Finset.range d,
weight w (randomizedBatching σ w n d k E z) := by sorry
end HyperMatchDelay.Batching
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.