Lemma 3.3 — a step toward the maximum-cost point lowers by at least
ProvedFracPackCover.Covering.lemma_3_3fractional-coveringp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1potential-function
Let , , be covering data and a bound on the width ( for all and all ). Let , and ; let be the dual solution corresponding to and its potential. Suppose and do not satisfy . Let attain the maximum of over , and let . Put and let be the potential of (same ). Then
This is the progress lemma of the covering algorithm: as long as fails, every update of IMPROVE-COVER decreases the potential by a constant factor.
Formalization Note The step is assumed nonnegative, as it is in Figure 3.
Preamble
import Mathlib import Definitions.Def_FracPackCover_Covering_Basic
Formal statement
namespace FracPackCover.Covering
/-- Lemma 3.3 (Plotkin–Shmoys–Tardos, Cornell ORIE TR 999, p. 19). Let `x ∈ P`, `0 < ε ≤ 1`,
`α > 0`, and let `y` be the dual solution corresponding to `x` (parameter `α`), with potential
`Φ = yᵗb`, such that `x, y` do not satisfy 𝒞2. Let `x̃ ∈ P` attain the maximum `C_𝒞(y)` of `yᵗ A x`
over `P`, let `ρ` bound the width, and let `0 ≤ σ ≤ ε/(4αρ)`. For `x̂ = (1 − σ) x + σ x̃` with
potential `Φ̂` (same `α`), `Φ − Φ̂ ≥ ε α σ Φ`. -/
theorem lemma_3_3 {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ)
(P : Set (Fin n → ℝ)) (hdata : IsCoveringData A b P) (ρ : ℝ) (hρ : WidthBound A b P ρ)
(x xt : Fin n → ℝ) (hx : x ∈ P) (hxt : xt ∈ P)
(ε α σ : ℝ) (hε : 0 < ε) (hε1 : ε ≤ 1) (hα : 0 < α) (hσ0 : 0 ≤ σ)
(hσ : σ ≤ ε / (4 * α * ρ))
(hmax : ∀ x' ∈ P, yAx A (dualY A b α x) x' ≤ yAx A (dualY A b α x) xt)
(hC2 : ¬ C2 A b ε (dualY A b α x) x (yAx A (dualY A b α x) xt)) :
ε * α * σ * potential A b α x ≤
potential A b α x - potential A b α ((1 - σ) • x + σ • xt) := 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. 19, Lemma 3.3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.