Lemma 4, p. 14 — Greedy is 1/k-competitive for k-Max-Matching
ProvedHyperMatchDelay.Batching.lemma_4Let and let be a finite family of hyperedges, each with at most vertices and non-negative weight (a weighted hypergraph of rank at most ). Run Greedy (Algorithm 5): scan the edges in non-increasing order of weight, with ties broken in any way, and keep each edge that is disjoint from the edges kept so far. Then the output is a matching of , and for every matching of
In particular Greedy achieves at least a fraction of the maximum weight matching, i.e. its competitive ratio for k-Max-Matching is at least . This classical guarantee (also known for weighted -set packing) is used inside Depth-k Greedy to handle the short edges of each batch.
Formalization Note The ordering with arbitrary ties is an oracle satisfying the sorted-order predicate; the statement holds for every such oracle. The running-time clause of Lemma 4, , is not formalized.
import Mathlib import Definitions.Def_HyperMatchDelay_Batching_Model
namespace HyperMatchDelay.Batching
/-- Lemma 4, p. 14 (competitive clause): on a rank-`k` hypergraph with non-negative weights,
Greedy (Algorithm 5, with any weight-sorted order) returns a matching whose weight is at least
`1/k` times the weight of every matching. -/
theorem lemma_4 (k : ℕ) (hk : 1 ≤ k) (w : Finset ℕ → ℝ)
(σ : Finset (Finset ℕ) → List (Finset ℕ)) (hσ : IsSortedOrder w σ)
(S : Finset (Finset ℕ)) (hS : ∀ e ∈ S, e.card ≤ k ∧ 0 ≤ w e) :
IsMatching S (greedy σ S) ∧
∀ M, IsMatching S M → (1 / (k : ℝ)) * weight w M ≤ weight w (greedy σ S) := by sorry
end HyperMatchDelay.Batching
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.