Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.5 — an ε-relaxed decision procedure for Ax ≤ b, x ∈ P with O(ρ²ε⁻²log(mρ/ε)) oracle calls

Proved
FracPackCover.General.theorem_4_5

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

approximation-algorithmscomplexitylagrangean-relaxationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let AAA be an arbitrary real m×nm\times nm×n matrix, b∈Rmb \in \mathbb R^mb∈Rm arbitrary, d∈Rmd \in \mathbb R^md∈Rm with d>0d > 0d>0, and P⊆RnP \subseteq \mathbb R^nP⊆Rn convex. Let ρ>0\rho > 0ρ>0 bound the width, ∣aix−bi∣≤ρdi|a_i x - b_i| \le \rho d_i∣ai​x−bi​∣≤ρdi​ for all x∈Px \in Px∈P and all iii, and let orc\mathrm{orc}orc be any exact minimizing oracle for PPP and AAA (subroutine (10)). For every ε\varepsilonε with 0<ε<10 < \varepsilon < 10<ε<1 and every starting point x0∈Px_0 \in Px0​∈P, the driver that calls IMPROVE-GENERAL repeatedly:

  1. stops;
  2. if it outputs a point xxx, then x∈Px \in Px∈P and Ax≤b+εdAx \le b + \varepsilon dAx≤b+εd (xxx is an ε\varepsilonε-approximate solution);
  3. if it reports infeasibility, then there is no exact solution: no x∈Px \in Px∈P satisfies Ax≤bAx \le bAx≤b;
  4. it makes at most
N=2(⌊log⁡2(ρ/ε)⌋+1)+11520 ρ2ε2 ln⁡ ⁣(12 m max⁡(ρ,ε)ε)N = 2\big(\lfloor \log_2(\rho/\varepsilon)\rfloor + 1\big) + 11520\,\frac{\rho^2}{\varepsilon^2}\,\ln\!\Big(\frac{12\, m\, \max(\rho,\varepsilon)}{\varepsilon}\Big)N=2(⌊log2​(ρ/ε)⌋+1)+11520ε2ρ2​ln(ε12mmax(ρ,ε)​)

calls to subroutine (10).

This is the paper's main result for the GENERAL problem: an ε\varepsilonε-relaxed decision procedure whose number of optimization-oracle calls depends on the width ρ\rhoρ, the accuracy ε\varepsilonε and only logarithmically on the number of constraints.

Formalization Note. The paper writes O(ρ2ε−2log⁡(mρε−1))O(\rho^2\varepsilon^{-2}\log(m\rho\varepsilon^{-1}))O(ρ2ε−2log(mρε−1)); its proof yields NNN above: each call made with λ0>ε\lambda_0 > \varepsilonλ0​>ε costs at most 2+8640ρ2λ0−2ln⁡(12mρ/λ0)2 + 8640\rho^2\lambda_0^{-2}\ln(12m\rho/\lambda_0)2+8640ρ2λ0−2​ln(12mρ/λ0​) calls (Theorem 4.4), λ0\lambda_0λ0​ more than halves between calls, so ∑λ0−2<43ε−2\sum \lambda_0^{-2} < \tfrac43\varepsilon^{-2}∑λ0−2​<34​ε−2 and there are at most ⌊log⁡2(ρ/ε)⌋+1\lfloor\log_2(\rho/\varepsilon)\rfloor + 1⌊log2​(ρ/ε)⌋+1 calls. The max⁡(ρ,ε)\max(\rho,\varepsilon)max(ρ,ε) equals ρ\rhoρ whenever any call is made (it only keeps NNN nonnegative when ρ<ε\rho < \varepsilonρ<ε, a case in which every point of PPP is already ε\varepsilonε-approximate); ⌊⋅⌋\lfloor\cdot\rfloor⌊⋅⌋ is the floor truncated at 000. IMPROVE-GENERAL uses λ0/2\lambda_0/2λ0​/2 in place of λ0\lambda_0λ0​ in Figure 4's α\alphaα and σ\sigmaσ (see the procedure's definition). The driver is run with a fuel bound, and the theorem asserts it stops for every fuel ≥N\ge N≥N. The "time to compute AxAxAx" part of the paper's statement is not formalized.


Retired 2026-10-27: a Lean-vs-paper fidelity audit found this statement weaker than, or narrower than, the cited result. A corrected statement will be resubmitted.

Preamble
import Mathlib
import Definitions.Def_FracPackCover_General_Driver
Formal statement
namespace FracPackCover.General

/-- Theorem 4.5 (p. 27), for the driver over IMPROVE-GENERAL with the corrected parameters.
For every `ε ∈ (0,1)`, every start `x₀ ∈ P` and every exact minimizing oracle, the driver run with
any fuel `≥ N` stops; if it outputs `x` then `x ∈ P` and `Ax ≤ b + εd`; if it reports
infeasibility then no `x ∈ P` has `Ax ≤ b`; and it makes at most
`N = 2(⌊log₂(ρ/ε)⌋ + 1) + 11520 ρ² ε⁻² ln(12 m max(ρ,ε)/ε)` oracle calls (the paper writes
`O(ρ²ε⁻² log(mρε⁻¹))`). -/
theorem theorem_4_5 {m n : ℕ} [NeZero m] (A : Matrix (Fin m) (Fin n) ℝ) (b d : Fin m → ℝ)
    (P : Set (Fin n → ℝ)) (hP : Convex ℝ P) (hd : ∀ i, 0 < d i)
    (ρ : ℝ) (hρ : 0 < ρ) (hW : WidthBound A b d P ρ)
    (orc : (Fin m → ℝ) → (Fin n → ℝ)) (horc : IsMinOracle P A orc)
    (x0 : Fin n → ℝ) (hx0 : x0 ∈ P) (ε : ℝ) (hε0 : 0 < ε) (hε1 : ε < 1) (fuel : ℕ)
    (hfuel : 2 * ((⌊Real.logb 2 (ρ / ε)⌋₊ : ℝ) + 1)
        + 11520 * ρ ^ 2 / ε ^ 2 * Real.log (12 * m * max ρ ε / ε) ≤ (fuel : ℝ)) :
    (generalDriver A b d ρ ε orc fuel x0).outcome ≠ DriverOutcome.outOfFuel ∧
    (∀ x, (generalDriver A b d ρ ε orc fuel x0).outcome = DriverOutcome.approx x →
        x ∈ P ∧ ∀ i, FracPackCover.Covering.rowVal A x i ≤ b i + ε * d i) ∧
    ((generalDriver A b d ρ ε orc fuel x0).outcome = DriverOutcome.infeasible →
        ¬ ∃ x ∈ P, ∀ i, FracPackCover.Covering.rowVal A x i ≤ b i) ∧
    ((generalDriver A b d ρ ε orc fuel x0).calls : ℝ) ≤
        2 * ((⌊Real.logb 2 (ρ / ε)⌋₊ : ℝ) + 1)
          + 11520 * ρ ^ 2 / ε ^ 2 * Real.log (12 * m * max ρ ε / ε) := by sorry

end FracPackCover.General
Source
Plotkin, Shmoys, Tardos, Fast Approximation Algorithms for Fractional Packing and Covering Problems, Cornell ORIE Tech. Rep. 999 (1992), p. 27, Theorem 4.5 (for Figure 4 with λ₀/2-corrected parameters)
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