Theorem 3.2 (covering half, set cover) — the scheme is -competitive for fractional covering
ProvedBNCovPack.SetCover.theorem_3_2Let be a finite set of elements and a finite family of sets with positive costs , and for an element let be the sets containing . Elements arrive in a list ; suppose every arriving element lies in at least one set and in at most sets, , with . Let and let be the weights produced by the Section 3 fractional scheme with coefficients and replaced by after processing . Then:
- is a fractional cover of the arrived elements: for every ;
- for every fractional cover of the arrived elements ( for every ),
This is the covering half of Theorem 3.2 of the paper, in the set-cover form used in Section 5.1: the fractional algorithm is -competitive whatever the value of . In Section 5.1 it supplies the bound that turns the potential-function argument into the guarantee.
Formalization Note The paper writes ; the proof of Theorem 3.1, with replaced by and , yields (claim (i) gives , and claim (iii) with makes dual feasible). The packing half of Theorem 3.2 (the dual solution does not violate the packing constraints) is not stated here. Logarithms are natural. The statement holds for every list , hence at every time of the run. The frequency bound is required only of arriving elements, as in the paper ("each primal constraint consists of at most non-zero coefficients").
import Mathlib import Definitions.Def_OnlinePrimalDual_OnlineSetCover_SetCoverInstance import Definitions.Def_OnlinePrimalDual_OnlineSetCover_elementWeight import Definitions.Def_BNCovPack_SetCover_FracScheme
namespace BNCovPack.SetCover
open OnlinePrimalDual.OnlineSetCover
/-- **Theorem 3.2** (Buchbinder–Naor 2009, p. 5), covering half, on a set-cover instance
(`a ∈ {0,1}`): if every arriving constraint (element `e`) has at most `ℓ` non-zero coefficients
(`|𝒮_e| ≤ ℓ`), then for every `B > 0` the Section 3 scheme with `n` replaced by `ℓ`
(i) produces a feasible fractional cover of the arrived elements, and
(ii) has primal cost at most `2 ln(1 + ℓ)` times the cost of any fractional cover of them.
The paper writes `O(log ℓ)`; the proof of Theorem 3.1 with `n → ℓ` yields `2 ln(1 + ℓ)`. -/
theorem theorem_3_2 {E T : Type*} [Fintype E] [Fintype T] [DecidableEq T]
(inst : SetCoverInstance E T) (B : ℝ) (hB : 0 < B) (ℓ : ℕ) (hℓ : 1 ≤ ℓ)
(σ : List E) (hfreq : ∀ e ∈ σ, (inst.elemSets e).card ≤ ℓ)
(hσ : ∀ e ∈ σ, (inst.elemSets e).Nonempty) :
(∀ e ∈ σ, 1 ≤ elementWeight inst (fracRun inst B ℓ σ).w e) ∧
∀ w'' : T → ℝ, (∀ s, 0 ≤ w'' s) → (∀ e ∈ σ, 1 ≤ elementWeight inst w'' e) →
∑ s, inst.c s * (fracRun inst B ℓ σ).w s
≤ 2 * Real.log (1 + (ℓ : ℝ)) * ∑ s, inst.c s * w'' s := by sorry
end BNCovPack.SetCover
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.