Observation 1, p. 6 — every hyperedge e lies in E_z for at least d − diam(e) shifts z
ProvedHyperMatchDelay.Batching.observation_1batchinghypergraph-matchingonline-algorithmsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a shareability hypergraph with parameters and . For a shift let be the set of hyperedges contained in a single batch window . Then every hyperedge survives the batching for many shifts:
Since , every hyperedge lies in for at least one shift, and a hyperedge of diameter at most for at least shifts. This counting fact is what turns per-batch guarantees into the competitive ratio.
Formalization Note The left-hand side is the number of with ; is a natural-number difference, exact here because .
Preamble
import Mathlib import Definitions.Def_HyperMatchDelay_Batching_Model
Formal statement
namespace HyperMatchDelay.Batching
/-- Observation 1, p. 6: every hyperedge `e` of a shareability hypergraph lies in `E_z` for at
least `d - diam(e)` of the `d` shifts `z ∈ {0, …, d - 1}`. -/
theorem observation_1 (n d k : ℕ) (hd : 1 ≤ d) (E : Finset (Finset ℕ))
(w : Finset ℕ → ℝ) (hE : IsShareability n d k E w) (e : Finset ℕ) (he : e ∈ E) :
d - diam e ≤ ((Finset.range d).filter (fun z => e ∈ shiftEdges E n d z)).card := by sorry
end HyperMatchDelay.Batching
Source
Pavone, Saberi, Schiffer & Tsao, Online Hypergraph Matching with Delays, arXiv:2009.12022v1, p. 6, Observation 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.