Lemma 3.1 — 𝒞1 and 𝒞2 certify infeasibility when , and -optimality otherwise
ProvedFracPackCover.Covering.lemma_3_1dualityfractional-coveringp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1relaxed-optimality
Let , and a nonempty convex in the nonnegative orthant be covering data, and let . Let with , and let , . Let maximize over and put . Suppose that and satisfy the relaxed optimality conditions
Then:
- if , there is no exact solution, i.e. no with ;
- if , then is -optimal: for every .
This lemma turns the two relaxed optimality conditions into the two outcomes of the covering algorithm: a certificate that no exact solution exists, or a near-optimal point from which -scaling continues.
Formalization Note " is -optimal", i.e. with the value of (8), is stated without as the inequality for every . The hypotheses and are implicit in the paper: for both conditions hold and both conclusions can fail, and the proof divides by . The algorithm uses the lemma with .
Preamble
import Mathlib import Definitions.Def_FracPackCover_Covering_Basic
Formal statement
namespace FracPackCover.Covering
/-- Lemma 3.1 (Plotkin–Shmoys–Tardos, Cornell ORIE TR 999, p. 17). Let `(x, λ)` with `x ∈ P`,
`λ = λ(x)`, and `y ≥ 0`, `y ≠ 0` be feasible primal and dual solutions satisfying 𝒞1 and 𝒞2, where
`C_𝒞(y) = yᵗ A x̃` for a maximizer `x̃ ∈ P` of `yᵗ A x` over `P`. If `λ ≤ 1 − 3ε` there is no exact
solution; if `λ ≥ 1 − 3ε`, `x` is `3ε`-optimal: `(1 − 3ε) λ(x') ≤ λ` for every `x' ∈ P`.
The hypotheses `y ≠ 0` and `0 < ε < 1/3` are implicit in the paper's proof. -/
theorem lemma_3_1 {m n : ℕ} [NeZero m] (A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ)
(P : Set (Fin n → ℝ)) (hdata : IsCoveringData A b P)
(ε : ℝ) (hε : 0 < ε) (hε3 : ε < 1 / 3)
(x : Fin n → ℝ) (hx : x ∈ P) (y : Fin m → ℝ) (hy : ∀ i, 0 ≤ y i) (hy0 : y ≠ 0)
(xt : Fin n → ℝ) (hxt : xt ∈ P) (hmax : ∀ x' ∈ P, yAx A y x' ≤ yAx A y xt)
(hC1 : C1 A b ε (lam A b x) y x) (hC2 : C2 A b ε y x (yAx A y xt)) :
(lam A b x ≤ 1 - 3 * ε → ¬ ∃ x' ∈ P, ∀ i, b i ≤ rowVal A x' i) ∧
(1 - 3 * ε ≤ lam A b x → ∀ x' ∈ P, (1 - 3 * ε) * lam A b x' ≤ lam A b 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. 17–18, Lemma 3.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.