Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.2 (covering half, set cover) — the {0,1}\{0,1\}{0,1} scheme is 2ln⁡(1+ℓ)2\ln(1+\ell)2ln(1+ℓ)-competitive for fractional covering

Proved
BNCovPack.SetCover.theorem_3_2

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

linear-programmingonline-algorithmsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1primal-dualset-cover

Let XXX be a finite set of elements and S\mathcal SS a finite family of sets with positive costs c(s)c(s)c(s), and for an element eee let Se\mathcal S_eSe​ be the sets containing eee. Elements arrive in a list σ\sigmaσ; suppose every arriving element lies in at least one set and in at most ℓ\ellℓ sets, 1≤∣Se∣≤ℓ1\le|\mathcal S_e|\le\ell1≤∣Se​∣≤ℓ, with ℓ≥1\ell\ge 1ℓ≥1. Let B>0B>0B>0 and let www be the weights produced by the Section 3 fractional scheme with {0,1}\{0,1\}{0,1} coefficients and nnn replaced by ℓ\ellℓ after processing σ\sigmaσ. Then:

  1. www is a fractional cover of the arrived elements: ∑s∈Sew(s)≥1\sum_{s\in\mathcal S_e}w(s)\ge 1∑s∈Se​​w(s)≥1 for every e∈σe\in\sigmae∈σ;
  2. for every fractional cover w′′≥0w''\ge 0w′′≥0 of the arrived elements (∑s∈Sew′′(s)≥1\sum_{s\in\mathcal S_e}w''(s)\ge1∑s∈Se​​w′′(s)≥1 for every e∈σe\in\sigmae∈σ),
∑s∈Sc(s) w(s) ≤ 2ln⁡(1+ℓ)∑s∈Sc(s) w′′(s).\sum_{s\in\mathcal S}c(s)\,w(s)\ \le\ 2\ln(1+\ell)\sum_{s\in\mathcal S}c(s)\,w''(s).s∈S∑​c(s)w(s) ≤ 2ln(1+ℓ)s∈S∑​c(s)w′′(s).

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 O(log⁡ℓ)O(\log\ell)O(logℓ)-competitive whatever the value of BBB. In Section 5.1 it supplies the bound ∑sw(s)≤2ln⁡(1+d) OPT\sum_s w(s)\le 2\ln(1+d)\,OPT∑s​w(s)≤2ln(1+d)OPT that turns the potential-function argument into the O(log⁡dlog⁡(n/OPT))O(\log d\log(n/OPT))O(logdlog(n/OPT)) guarantee.

Formalization Note The paper writes O(log⁡ℓ)O(\log\ell)O(logℓ); the proof of Theorem 3.1, with nnn replaced by ℓ\ellℓ and a(i,j)∈{0,1}a(i,j)\in\{0,1\}a(i,j)∈{0,1}, yields 2ln⁡(1+ℓ)2\ln(1+\ell)2ln(1+ℓ) (claim (i) gives X≤BYX\le BYX≤BY, and claim (iii) with x(s)≤1x(s)\le 1x(s)≤1 makes yB/(2ln⁡(1+ℓ))yB/(2\ln(1+\ell))yB/(2ln(1+ℓ)) 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 σ\sigmaσ, 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 ℓ\ellℓ non-zero coefficients").

Preamble
import Mathlib
import Definitions.Def_OnlinePrimalDual_OnlineSetCover_SetCoverInstance
import Definitions.Def_OnlinePrimalDual_OnlineSetCover_elementWeight
import Definitions.Def_BNCovPack_SetCover_FracScheme
Formal statement
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
Source
Buchbinder, Naor, Online Primal-Dual Algorithms for Covering and Packing, Math. Oper. Res. (2009), DOI 10.1287/moor.1080.0363, p. 5, Theorem 3.2 (covering half); explicit constant from the proof of Theorem 3.1, pp. 5-6, claims (i)-(iii), with n replaced by ℓ
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me