Lemma 3.2 — a large enough makes the exponential dual satisfy 𝒞1
ProvedFracPackCover.Covering.lemma_3_2fractional-coveringp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1potential-functionrelaxed-optimality
Let , , be covering data, and let with . Let and
Then and its corresponding dual solution satisfy :
With the value of chosen in IMPROVE-COVER, this lemma and Lemma 3.4 keep true throughout the procedure, so only has to be tested.
Formalization Note The hypothesis is implicit in the paper, whose bound on contains .
Preamble
import Mathlib import Definitions.Def_FracPackCover_Covering_Basic
Formal statement
namespace FracPackCover.Covering
/-- Lemma 3.2 (Plotkin–Shmoys–Tardos, Cornell ORIE TR 999, p. 18). If
`α ≥ 2 λ⁻¹ ε⁻¹ ln(4 m ε⁻¹)` and `0 < ε < 1`, then any feasible solution `(x, λ)` (`x ∈ P`,
`λ = λ(x) > 0`) and its corresponding dual solution `y_i = (1/b_i) e^{−α a_i x / b_i}` satisfy 𝒞1. -/
theorem lemma_3_2 {m n : ℕ} [NeZero m] (A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ)
(P : Set (Fin n → ℝ)) (hdata : IsCoveringData A b P)
(x : Fin n → ℝ) (hx : x ∈ P) (hlam : 0 < lam A b x)
(ε α : ℝ) (hε : 0 < ε) (hε1 : ε < 1)
(hα : 2 * (lam A b x)⁻¹ * ε⁻¹ * Real.log (4 * m * ε⁻¹) ≤ α) :
C1 A b ε (lam A b x) (dualY A b α x) x := 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. 18–19, Lemma 3.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.