Theorem 4.1 — Algorithm 1 (basic discrete algorithm): -competitive covering solution, -competitive integral packing solution with violation
ProvedOnlinePrimalDual.Framework.algorithm1_competitive_ratio_v2Consider the online packing–covering framework of Section 4.1: a covering LP subject to for every constraint and , whose constraints arrive online in the order ord (a permutation of ), and its packing dual subject to , . Assume for all , every constraint involves at least one variable (), and . Let be the output of Algorithm 1 (alg1Run inst ord): starting from , , each arriving constraint is processed by the inner loop "while : for each , ; ". Then
- the covering solution is feasible: for every ;
- the integral packing solution violates each packing constraint by a factor of at most : for every ;
- is -competitive: for every feasible covering solution ;
- is -competitive: for every feasible packing solution .
Formalization Note. The retired version took the iteration counts as a free variable constrained only by final primal feasibility, which is monotone in , so over-incremented runs (e.g. on a one-variable instance, violating bound 2) were admitted. The new statement computes and by a definition (alg1Run) that executes Algorithm 1 literally — each constraint's inner loop runs exactly while the constraint is violated — so the theorem is about the algorithm's own output; feasibility of (the book's Claim (1)) is stated as a conclusion rather than assumed. Conventions made explicit: (the book's standing assumption for Algorithm 1, p. 118); for all (feasibility of the covering LP, the section's standing convention — otherwise the book's loop does not terminate; it also forces ); the arrival order is a permutation of ; competitiveness is stated by weak duality against every feasible offline solution of the opposite LP, as in the retired version, with the constants and transcribed from the captain's reading of the proof on p. 120. Correction to the printed source: none.
import Mathlib import Definitions.Def_OnlinePrimalDual_Framework_CoveringInstance import Definitions.Def_OnlinePrimalDual_Framework_dualSum import Definitions.Def_OnlinePrimalDual_Framework_alg1Run_v2
namespace OnlinePrimalDual.Framework
/-- **Theorem 4.1** (Buchbinder & Naor, FnT TCS 2009, p. 118-120), Algorithm 1, the basic discrete
algorithm. `ord` is the online arrival order of the covering constraints (`hord_nodup`/`hord_mem`:
a permutation of `J`); `alg1Run inst ord` is Algorithm 1's own output (p. 118, steps (1a)-(1b)
applied verbatim: each arriving constraint is processed by inner-loop iterations *exactly while*
it is still violated, and `yⱼ` counts them), so `x` and `y` below are computed from the instance
and the arrival order alone — the retired version let the iteration counts be a free variable
pinned only by final feasibility, which admits over-incremented runs. `hc1` is the book's standing
assumption `cᵢ ≥ 1` for this algorithm (p. 118); `hS` is the standing feasibility assumption of the
covering LP (every constraint involves at least one variable; otherwise the book's loop never
terminates). Conclusions: the covering solution is feasible (Claim (1), part of "produces a
covering solution"); the integral packing solution `y` violates each packing constraint by a
factor of at most `log₂(3d+1)` (Claims (2)-(3) with the proof's own displayed bound, p. 120); the
covering solution is `2·log₂(3d+1)`-competitive against every feasible offline covering solution;
the packing solution is `2`-competitive against every feasible offline packing solution
(`P ≤ 2D` and weak duality both ways). -/
theorem algorithm1_competitive_ratio_v2 {I J : Type*} [Fintype I] [Fintype J] [DecidableEq I]
[DecidableEq J] (inst : CoveringInstance I J) (hc1 : ∀ i, 1 ≤ inst.c i)
(hS : ∀ j, (inst.S j).Nonempty) (ord : List J)
(hord_nodup : ord.Nodup) (hord_mem : ∀ j, j ∈ ord) :
let x : I → ℝ := (alg1Run inst ord).1
let y : J → ℝ := fun j => ((alg1Run inst ord).2 j : ℝ)
(∀ j, 1 ≤ ∑ i ∈ inst.S j, x i) ∧
(∀ i : I, dualSum inst y i ≤ inst.c i * Real.logb 2 (3 * inst.d + 1)) ∧
(∀ x'' : I → ℝ, (∀ i, 0 ≤ x'' i) → (∀ j, 1 ≤ ∑ i ∈ inst.S j, x'' i) →
∑ i, inst.c i * x i ≤ 2 * Real.logb 2 (3 * inst.d + 1) * ∑ i, inst.c i * x'' i) ∧
(∀ y'' : J → ℝ, (∀ j, 0 ≤ y'' j) → (∀ i, dualSum inst y'' i ≤ inst.c i) →
∑ j, y'' j ≤ 2 * ∑ j, y j) := by sorry
end OnlinePrimalDual.Framework