Theorem 3.1, proof, claim (ii) — the primal solution produced by the scheme is feasible
ProvedBNCovPack.Packing.claim_iilinear-programmingonline-algorithmsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1primal-dual
Consider the online fractional packing scheme of Section 3 with parameter , run on an instance with primal variables, costs , non-negative coefficients , and columns each of which has at least one positive entry. Let denote the primal solution held by the scheme. Then:
- after every round , is feasible for the covering constraints revealed so far:
- no primal variable ever decreases: the value of after round is at least its value after round .
Feasibility of the primal solution is half of the weak-duality argument that turns claim (i) into -competitiveness. Part 2 is the paper's remark that "the values of the primal variables never decrease" (p. 5), which its proof of claim (ii) uses.
Formalization Note Columns are Fin m, 0-based, so "column " (1-based) is (k : ℕ) < r. The scheme is stateAfter of BNCovPack.Packing.Scheme.
Preamble
import Mathlib import Definitions.Def_OnlinePrimalDual_GeneralPacking_GeneralInstance import Definitions.Def_BNCovPack_Packing_Scheme
Formal statement
namespace BNCovPack.Packing
open OnlinePrimalDual.GeneralPacking
/-- Buchbinder–Naor 2009, proof of Theorem 3.1, claim (ii) (p. 5; proved p. 6): after every round
`r`, the primal solution `x` maintained by the scheme is feasible for the covering constraints
given so far (`x ≥ 0` and `∑ᵢ a(i,k) x(i) ≥ 1` for every column `k < r`), and no primal variable
ever decreases from one round to the next. -/
theorem claim_ii {I : Type*} [Fintype I] [Nonempty I] {m : ℕ}
(inst : GeneralInstance I (Fin m)) (B : ℝ) (hB : 0 < B)
(hcol : ∀ j : Fin m, ∃ i, 0 < inst.a i j) :
(∀ r : ℕ, r ≤ m →
(∀ i, 0 ≤ (stateAfter inst B r).x i) ∧
(∀ k : Fin m, (k : ℕ) < r → 1 ≤ ∑ i, inst.a i k * (stateAfter inst B r).x i)) ∧
(∀ r : ℕ, ∀ i, (stateAfter inst B r).x i ≤ (stateAfter inst B (r + 1)).x i) := by sorry
end BNCovPack.Packing
Source
Buchbinder, Naor, Online Primal-Dual Algorithms for Covering and Packing, Math. Oper. Res. (2009), DOI 10.1287/moor.1080.0363, p. 5, Theorem 3.1, proof, claim (ii) (proved p. 6); monotonicity: p. 5, line 2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.