Lemma 5.2 — the online algorithm covers every arriving element and chooses at most sets
ProvedBNCovPack.SetCover.lemma_5_2Consider online unweighted set cover: a ground set of elements, a finite family of sets, all of cost , and an upper bound on the frequency of every element (the number of sets containing it). Elements arrive in a list . Let be a natural number such that some family of at most sets covers every element of . Run the algorithm of Section 5.1 with any , any order of the sets, frequency parameter and the value , and let be the family it has chosen. Then:
- every element of is covered by a set of ;
- with and ,
Since , this is the paper's guarantee that the deterministic online algorithm is -competitive for online unweighted set cover, improving the of Alon et al. Because is arbitrary, both claims hold at every time of the run.
Formalization Note The paper writes ; the proof yields , from and the fractional bound . The paper assumes is known and equal to the optimum; here is any known upper bound on the optimum (at the optimum this is the paper's statement). may be any upper bound on the maximum frequency (at the maximum frequency this is the paper's statement). Unit costs are the hypothesis on the published instance type. The doubling wrapper for unknown is not part of the statement.
import Mathlib import Definitions.Def_OnlinePrimalDual_OnlineSetCover_SetCoverInstance import Definitions.Def_OnlinePrimalDual_OnlineSetCover_coveredBy import Definitions.Def_BNCovPack_SetCover_Potential import Definitions.Def_BNCovPack_SetCover_Algorithm
namespace BNCovPack.SetCover
open OnlinePrimalDual.OnlineSetCover
/-- **Lemma 5.2** (Buchbinder–Naor 2009, p. 14): the online unweighted set-cover algorithm of §5.1
(unit costs, fractional scheme with `ℓ = d`, rounding by the potential `Φ` with
`α = max {1, ln(r n/OPT)}`), run with any `B > 0`, any processing order of the sets, and a known
value `OPT ≥ 1` such that some family of at most `OPT` sets covers every arriving element,
(i) covers every element that is given to it, and
(ii) chooses at most `(2 α ln(1 + d) + 1) · OPT / ln 2` sets.
The paper writes `OPT · O(log d log(n/OPT))`; the proof yields `(2α ln(1+d) + 1)·OPT/ln 2`. -/
theorem lemma_5_2 {E T : Type*} [Fintype E] [Fintype T] [DecidableEq T]
(inst : SetCoverInstance E T) (hc : ∀ s, inst.c s = 1)
(B : ℝ) (hB : 0 < B) (d : ℕ) (hd : 1 ≤ d) (hfreq : ∀ e, (inst.elemSets e).card ≤ d)
(OPT : ℕ) (hOPT : 1 ≤ OPT) (ord : List T) (hord : ∀ s, s ∈ ord) (σ : List E)
(hopt : ∃ F : Finset T, F.card ≤ OPT ∧ ∀ e ∈ σ, coveredBy inst F e) :
(∀ e ∈ σ, coveredBy inst (run inst B d OPT ord σ).cover e) ∧
((run inst B d OPT ord σ).cover.card : ℝ)
≤ (2 * alphaParam (Fintype.card E) OPT * Real.log (1 + (d : ℝ)) + 1) * (OPT : ℝ)
/ Real.log 2 := by sorry
end BNCovPack.SetCover
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.