Lemma 3.6 — with oracle calls, an initial with or a proof that no exact solution exists
ProvedFracPackCover.Covering.lemma_3_6fractional-coveringinitializationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , , be covering data and let subroutine (7) be an exact maximization oracle. The initial-solution procedure calls the oracle once for each row , with costs , obtaining that maximizes over ( calls in all), and then:
- if for some , it reports that there is no exact solution, and indeed no has ;
- otherwise it returns , which lies in and satisfies
This provides the starting point of the covering algorithm, with .
Preamble
import Mathlib import Definitions.Def_FracPackCover_Covering_Basic import Definitions.Def_FracPackCover_Covering_Driver
Formal statement
namespace FracPackCover.Covering
/-- Lemma 3.6 (Plotkin–Shmoys–Tardos, Cornell ORIE TR 999, p. 20). The initial-solution procedure
`initCover`, which makes `m` calls to subroutine (7) (one with costs `a_i` for each row `i`), either
finds `x ∈ P` with `A x ≥ (1/m) b`, or correctly concludes that there is no exact solution. -/
theorem lemma_3_6 {m n : ℕ} [NeZero m] (A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ)
(P : Set (Fin n → ℝ)) (hdata : IsCoveringData A b P)
(orc : (Fin m → ℝ) → (Fin n → ℝ)) (horc : IsMaxOracle A P orc) :
(initCover A b orc = none → ¬ ∃ x' ∈ P, ∀ i, b i ≤ rowVal A x' i) ∧
(∀ x, initCover A b orc = some x → x ∈ P ∧ ∀ i, (1 / (m : ℝ)) * b i ≤ rowVal A x i) := 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. 20, Lemma 3.6
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.