Lemma 3.4 — during IMPROVE-COVER,
ProvedFracPackCover.Covering.lemma_3_4fractional-coveringp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1potential-function
Let , , be covering data, a width bound, and let subroutine (7) be an exact maximization oracle. Let and run IMPROVE-COVER (Figure 3) from with . Then throughout the execution the current solution satisfies
Precisely: if is the point after updates and the while-test of Figure 3 held at , then .
Combined with Lemma 3.2 and the choice , this shows that holds at every point of the run.
Formalization Note The statement is about the states of the run of Figure 3, not about an arbitrary point: "reached" means the while-test held at every earlier state.
Preamble
import Mathlib import Definitions.Def_FracPackCover_Covering_Basic import Definitions.Def_FracPackCover_Covering_ImproveCover
Formal statement
namespace FracPackCover.Covering
/-- Lemma 3.4 (Plotkin–Shmoys–Tardos, Cornell ORIE TR 999, p. 19). Let `0 < ε < 1` and let
IMPROVE-COVER(x, ε) (Figure 3) start from `x ∈ P` with `λ0 = λ(x) > 0`, width bound `ρ` and an
exact maximization oracle. Then every point `(x_t, λ_t)` reached during its execution has
`λ_t ≥ 3λ0/4`. -/
theorem lemma_3_4 {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)
(x : Fin n → ℝ) (hx : x ∈ P) (hlam : 0 < lam A b x) (ε : ℝ) (hε : 0 < ε) (hε1 : ε < 1)
(t : ℕ) (ht : IsReachedCover A b orc ρ ε x t) :
3 * lam A b x / 4 ≤ lam A b (coverIterate A b orc ρ ε x t) := by sorry
end FracPackCover.Covering
Source
Plotkin, Shmoys, Tardos, Fast Approximation Algorithms for Fractional Packing and Covering Problems, Cornell ORIE Tech. Rep. 999 (1992), pp. 19–20, Lemma 3.4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.