Theorem 4.2 — Algorithm 2 (the continuous algorithm) produces a feasible packing solution and -competitive covering and packing solutions
ProvedOnlinePrimalDual.Framework.algorithm2_competitive_ratio_v2In the online packing–covering framework of Section 4.1 (covering LP , , ; packing dual , , ; ; constraints arriving in the order ord, a permutation of ; every non-empty), let be the final dual vector of Algorithm 2 (raiseRun inst (alg2X inst) ord): starting from , when constraint arrives, is increased continuously while , where throughout (alg2X), and let be the final primal vector. Then
- is a feasible covering solution;
- is a feasible packing solution: and for every (no violation);
- is -competitive: for every feasible covering solution ;
- is -competitive: for every feasible packing solution .
Formalization Note. The retired version took as a free non-negative vector constrained only by final covering feasibility, so inflating past the point where its constraint is covered (e.g. on a one-variable instance) kept the hypotheses and broke packing feasibility. The new statement computes by a definition (raiseRun) that raises each arriving dual variable exactly until its constraint is covered — the infimum of the admissible stopping values, which the monotone, continuous and unbounded rule alg2X attains — so the theorem is about Algorithm 2's own output; Claim (1) is a conclusion rather than a hypothesis. Conventions made explicit: for all (feasibility of the covering LP, the section's standing convention; it also excludes the junk value ); the arrival order is a permutation of ; competitiveness is stated by weak duality against every feasible offline solution of the opposite LP; packing feasibility includes . 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_alg2X import Definitions.Def_OnlinePrimalDual_Framework_raiseRun_v2
namespace OnlinePrimalDual.Framework
/-- **Theorem 4.2** (Buchbinder & Naor, FnT TCS 2009, p. 121-122), Algorithm 2, the continuous
algorithm. `ord` is the online arrival order of the covering constraints (a permutation of `J`);
`y = raiseRun inst (alg2X inst) ord` is Algorithm 2's own final dual vector (p. 121: each arriving
`yⱼ` is increased continuously *exactly while* `∑_{i ∈ S(j)} xᵢ < 1`, with `x` given by the
closed-form rule `alg2X`), and `x = alg2X inst y` its final primal vector — both computed from
the instance and the arrival order alone. The retired version took `y` as a free vector pinned
only by final covering feasibility, which admits inflated `y`. `hS` is the standing feasibility
assumption of the covering LP (every constraint involves at least one variable). Conclusions:
the covering solution is feasible (Claim (1)); the packing solution `y` is exactly feasible
(Claim (3), p. 122: non-negative and `∑_{j | i ∈ S(j)} yⱼ ≤ cᵢ`); the covering solution is
`2 ln(1+d)`-competitive against every feasible offline covering solution (Eq. (4.2),
`∂P/∂yⱼ ≤ 2 ln(1+d) · ∂D/∂yⱼ`, and weak duality); the packing solution is `2 ln(1+d)`-competitive
against every feasible offline packing solution. -/
theorem algorithm2_competitive_ratio_v2 {I J : Type*} [Fintype I] [Fintype J] [DecidableEq I]
[DecidableEq J] (inst : CoveringInstance I J) (hS : ∀ j, (inst.S j).Nonempty)
(ord : List J) (hord_nodup : ord.Nodup) (hord_mem : ∀ j, j ∈ ord) :
let y : J → ℝ := raiseRun inst (alg2X inst) ord
let x : I → ℝ := alg2X inst y
(∀ j, 1 ≤ ∑ i ∈ inst.S j, x i) ∧
((∀ j, 0 ≤ y j) ∧ ∀ i : I, dualSum inst y i ≤ inst.c i) ∧
(∀ x'' : I → ℝ, (∀ i, 0 ≤ x'' i) → (∀ j, 1 ≤ ∑ i ∈ inst.S j, x'' i) →
∑ i, inst.c i * x i ≤ 2 * Real.log (1 + inst.d) * ∑ i, inst.c i * x'' i) ∧
(∀ y'' : J → ℝ, (∀ j, 0 ≤ y'' j) → (∀ i, dualSum inst y'' i ≤ inst.c i) →
∑ j, y'' j ≤ 2 * Real.log (1 + inst.d) * ∑ j, y j) := by sorry
end OnlinePrimalDual.Framework