Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.7 — an ε\varepsilonε-relaxed decision procedure for fractional covering with O(m+ρlog⁡2m+ε−2ρlog⁡(m/ε))O(m+\rho\log^2m+\varepsilon^{-2}\rho\log(m/\varepsilon))O(m+ρlog2m+ε−2ρlog(m/ε)) oracle calls

Proved
FracPackCover.Covering.theorem_3_7

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

approximation-algorithmsfractional-coveringp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1running-time

Let A∈Rm×nA\in\mathbb R^{m\times n}A∈Rm×n be nonnegative, b>0b>0b>0, and PPP a nonempty convex set in the nonnegative orthant of Rn\mathbb R^nRn. Let ρ>0\rho>0ρ>0 satisfy aix≤ρ bia_ix\le\rho\,b_iai​x≤ρbi​ for every x∈Px\in Px∈P and every row iii, and let subroutine (7) be any exact oracle that, given y≥0y\ge0y≥0, returns a point of PPP maximizing ytAxy^tAxytAx. Let 0<ε0<10<\varepsilon_0<10<ε0​<1 and put

N=m+(⌈log⁡2m⌉+1)(2+4320 ρln⁡(24m))+2⌈log⁡2ε0−1⌉+9408 ρ ε0−2ln⁡24mε0.N=m+\big(\lceil\log_2m\rceil+1\big)\big(2+4320\,\rho\ln(24m)\big)+2\big\lceil\log_2\varepsilon_0^{-1}\big\rceil+9408\,\rho\,\varepsilon_0^{-2}\ln\frac{24m}{\varepsilon_0}.N=m+(⌈log2​m⌉+1)(2+4320ρln(24m))+2⌈log2​ε0−1​⌉+9408ρε0−2​lnε0​24m​.

Then the covering algorithm of §3 (the initial solution of Lemma 3.6, calls to IMPROVE-COVER with ε=1/6\varepsilon=1/6ε=1/6, then ε\varepsilonε-scaling) stops after at most NNN calls to subroutine (7), and either

  1. returns x∈Px\in Px∈P with Ax≥(1−ε0)bAx\ge(1-\varepsilon_0)bAx≥(1−ε0​)b (an ε0\varepsilon_0ε0​-approximate solution), or
  2. reports that no exact solution exists, and indeed no x∈Px\in Px∈P satisfies Ax≥bAx\ge bAx≥b.

This is the main result of §3: the fractional covering problem is decided, up to the relaxation ε0\varepsilon_0ε0​, with a number of optimization-oracle calls that depends on the width ρ\rhoρ but not on nnn or on the structure of PPP.

Formalization Note The paper writes O(m+ρlog⁡2m+ε−2ρlog⁡(mε−1))O(m+\rho\log^2m+\varepsilon^{-2}\rho\log(m\varepsilon^{-1}))O(m+ρlog2m+ε−2ρlog(mε−1)); its proof yields the explicit NNN above: mmm calls for the initial solution, at most ⌈log⁡2m⌉+1\lceil\log_2m\rceil+1⌈log2​m⌉+1 calls of IMPROVE-COVER with ε=1/6\varepsilon=1/6ε=1/6 at 2+4320ρln⁡(24m)2+4320\rho\ln(24m)2+4320ρln(24m) oracle calls each (Theorem 3.5, part 1), and at most ⌈log⁡2ε0−1⌉\lceil\log_2\varepsilon_0^{-1}\rceil⌈log2​ε0−1​⌉ scaling phases whose costs (Theorem 3.5, part 2) sum to at most 2⌈log⁡2ε0−1⌉+9408ρε0−2ln⁡(24m/ε0)2\lceil\log_2\varepsilon_0^{-1}\rceil+9408\rho\varepsilon_0^{-2}\ln(24m/\varepsilon_0)2⌈log2​ε0−1​⌉+9408ρε0−2​ln(24m/ε0​). The time to compute AxAxAx between calls is not counted. Termination is asserted, not assumed: the algorithm, run with ⌈N⌉\lceil N\rceil⌈N⌉ as the bound on every loop, returns an outcome. The quantification over every exact oracle and every width bound makes the bound uniform.

Preamble
import Mathlib
import Definitions.Def_FracPackCover_Covering_Basic
import Definitions.Def_FracPackCover_Covering_ImproveCover
import Definitions.Def_FracPackCover_Covering_Driver
Formal statement
namespace FracPackCover.Covering

/-- Theorem 3.7 (Plotkin–Shmoys–Tardos, Cornell ORIE TR 999, p. 21), with the explicit constants
of its proof. For `0 < ε₀ < 1`, every covering instance (`A ≥ 0`, `b > 0`, `P` convex, nonempty, in
the nonnegative orthant), every width bound `ρ` and every exact maximization oracle, the covering
algorithm of §3 (`coverAlgorithm`: initial solution, phase `ε = 1/6`, `ε`-scaling) stops, using at most
`N = m + (⌈log₂ m⌉ + 1)(2 + 4320 ρ ln(24m)) + 2⌈log₂(1/ε₀)⌉ + 9408 ρ ε₀⁻² ln(24m/ε₀)` calls to
subroutine (7) (the paper writes `O(m + ρ log² m + ε⁻² ρ log(m ε⁻¹))`), and either returns `x ∈ P`
with `A x ≥ (1 − ε₀) b` or reports that no `x ∈ P` has `A x ≥ b`, correctly. -/
theorem theorem_3_7 {m n : ℕ} [NeZero m] (A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ)
    (P : Set (Fin n → ℝ)) (hdata : IsCoveringData A b P) (ρ : ℝ) (hρ : WidthBound A b P ρ)
    (orc : (Fin m → ℝ) → (Fin n → ℝ)) (horc : IsMaxOracle A P orc)
    (ε₀ : ℝ) (hε₀ : 0 < ε₀) (hε₀1 : ε₀ < 1) :
    let N : ℝ := (m : ℝ) + ((⌈Real.logb 2 m⌉₊ : ℝ) + 1) * (2 + 4320 * ρ * Real.log (24 * m)) +
      2 * (⌈Real.logb 2 ε₀⁻¹⌉₊ : ℝ) + 9408 * ρ * ε₀⁻¹ ^ 2 * Real.log (24 * m * ε₀⁻¹)
    ∃ out : CoverOutcome n, ∃ c : ℕ,
      coverAlgorithm A b orc ρ ε₀ ⌈N⌉₊ = some (out, c) ∧ (c : ℝ) ≤ N ∧
      (∀ x, out = .approx x → x ∈ P ∧ ∀ i, (1 - ε₀) * b i ≤ rowVal A x i) ∧
      (out = .infeasible → ¬ ∃ x' ∈ P, ∀ i, b i ≤ rowVal A x' i) := by sorry

end FracPackCover.Covering
Source
Plotkin, Shmoys, Tardos, Fast Approximation Algorithms for Fractional Packing and Covering Problems, Cornell ORIE Tech. Rep. 999 (1992), p. 21, Theorem 3.7 (driver: pp. 20–21)
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