Theorem 3.1, proof, claim (i) — in each round
ProvedBNCovPack.Packing.claim_ilinear-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 and be the values of the primal and dual solutions after round . Then for every round ,
Together with primal feasibility (claim (ii)) and weak duality, this is what makes the scheme -competitive.
Formalization Note The scheme, and are stateAfter, primalValue and dualValue of BNCovPack.Packing.Scheme; is the initial state. The positivity of every column is the paper's standing assumption (p. 4), without which a round never terminates.
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 (i) (p. 5; proved pp. 5–6): in each round
`r`, the value `X` of the primal solution maintained by the online fractional packing scheme is
at most `B` times the value `Y` of its dual solution, `Y(r) ≥ X(r)/B`. -/
theorem claim_i {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 → primalValue inst B r ≤ B * dualValue inst B r := 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 (i) (proved pp. 5–6, displays (1)–(2))
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.