Lemma 5.1 (i) — initially , and at all times
ProvedBNCovPack.SetCover.lemma_5_1_iderandomizationonline-algorithmsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1potential-functionset-cover
Let be a ground set of elements, a finite family of sets, and a natural number. Let be the potential of Section 5.1, with and . Then:
- at start, when every weight is and no set is chosen,
- for every real , every weight vector and every family of sets, .
Together with Lemma 5.1 (ii), part 1 gives throughout the run of the algorithm, which is what Lemma 5.2 uses; part 2 is the positivity used to conclude that each term of is at most .
Formalization Note The page's proof writes "" and ""; the letter there is a misprint for , since the chosen only gives , and holds for with this . The statement uses . Positivity is stated for all states, not only those reached by the algorithm. is allowed (then ).
Preamble
import Mathlib import Definitions.Def_OnlinePrimalDual_OnlineSetCover_SetCoverInstance import Definitions.Def_BNCovPack_SetCover_Potential
Formal statement
namespace BNCovPack.SetCover
open OnlinePrimalDual.OnlineSetCover
/-- **Lemma 5.1 (i)** (Buchbinder–Naor 2009, p. 12; proof p. 13): at start (all weights `0`,
empty cover) `Φ ≤ 1` when `α = max {1, ln(r n / OPT)}`, `r = e ln(e/(e−1))`, `n = |E|`, and
`OPT ≥ 1`; and `Φ > 0` in every state (every weight vector `w`, every family `C`, every `α`). -/
theorem lemma_5_1_i {E T : Type*} [Fintype E] [Fintype T] [DecidableEq T]
(inst : SetCoverInstance E T) (OPT : ℕ) (hOPT : 1 ≤ OPT) :
potential inst (alphaParam (Fintype.card E) OPT) OPT (fun _ => 0) ∅ ≤ 1 ∧
∀ (α : ℝ) (w : T → ℝ) (C : Finset T), 0 < potential inst α OPT w C := by sorry
end BNCovPack.SetCover
Source
Buchbinder, Naor, Online Primal-Dual Algorithms for Covering and Packing, Math. Oper. Res. (2009), DOI 10.1287/moor.1080.0363, p. 12, Lemma 5.1 (i); proof p. 13 (α, r, initial value of Φ)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.