Lemma 4.2 — α ≥ 2λ⁻¹ln(6mρλ⁻¹) implies 𝒢1
ProvedFracPackCover.General.lemma_4_2lagrangean-relaxationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1potential-function
Let be as in the GENERAL problem with convex, and let satisfy for all and all . Let with , and let satisfy
Then and its corresponding dual solution satisfy : .
This says that the exponential dual solution makes the first relaxed optimality condition automatic once is large enough, so the algorithm only needs to test .
Formalization Note. is implicit in the paper ( and the logarithm appear); and the width bound are the section's standing assumptions.
Preamble
import Mathlib import Definitions.Def_FracPackCover_General_Basic
Formal statement
namespace FracPackCover.General
/-- Lemma 4.2 (p. 26). If `α ≥ 2λ⁻¹ ln(6mρλ⁻¹)`, where `λ = λ(x) > 0` for a point `x ∈ P` and
`ρ > 0` bounds the width of `P`, then `x` and its dual solution `y_i = d_i⁻¹ e^{α(a_ix − b_i)/d_i}`
satisfy (𝒢1). -/
theorem lemma_4_2 {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 ρ)
(x : Fin n → ℝ) (hx : x ∈ P) (hlam : 0 < lam A b d x) (α : ℝ)
(hα : 2 / lam A b d x * Real.log (6 * m * ρ / lam A b d x) ≤ α) :
G1 A b d x (lam A b d x) (dualVec A b d α x) := 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. 26, Lemma 4.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.