Theorem 4.3 — Algorithm 3 (complementary slackness): -competitive covering, -competitive packing with violation
DisprovedOnlinePrimalDual.Framework.algorithm3_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 3 (raiseRun inst (alg3X inst) ord): starting from , when constraint arrives, is increased continuously while , where throughout while , jumps to when reaches (step (1b)), and then (step (1c), frozen at ) — the closed form alg3X; let be the final primal vector. Then
- is a feasible covering solution;
- and 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 as a free non-negative vector constrained only by final covering feasibility, so a huge (e.g. on a one-variable instance) saturated every at , kept the hypotheses and violated the packing bound by an unbounded factor. 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, attained because alg3X is non-decreasing and right-continuous in and reaches — so the theorem is about Algorithm 3'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 excludes the junk value and gives , so ); the arrival order is a permutation of ; competitiveness is stated by weak duality against every feasible offline solution of the opposite LP, with the constants , and of the book's proof (Claims (2)-(3), p. 125-126). 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_alg3X import Definitions.Def_OnlinePrimalDual_Framework_raiseRun_v2
namespace OnlinePrimalDual.Framework
/-- **Theorem 4.3** (Buchbinder & Naor, FnT TCS 2009, p. 124-126), Algorithm 3, the
complementary-slackness algorithm — the goal of this mission. `ord` is the online arrival order
of the covering constraints (a permutation of `J`); `y = raiseRun inst (alg3X inst) ord` is
Algorithm 3's own final dual vector (p. 124: each arriving `yⱼ` is increased continuously
*exactly while* `∑_{i ∈ S(j)} xᵢ < 1`, with `x` given by the closed form `alg3X` of steps
(1b)-(1c)), and `x = alg3X 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, with the exact
constants the book's proof derives: the covering solution is feasible (Claim (1), p. 125); the
packing solution `y` is non-negative and violates each packing constraint by a factor of at most
`1 + ln d` (Claim (2), p. 125, "∑ yⱼ ≤ cᵢ(1 + ln d)"); the covering solution is
`2(1 + ln d)`-competitive against every feasible offline covering solution (Claim (3), `P ≤ 2D`,
p. 125-126, with the rescaled `y` and weak duality); the packing solution is `2`-competitive
against every feasible offline packing solution (`P ≤ 2D` and weak duality both ways). -/
theorem algorithm3_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 (alg3X inst) ord
let x : I → ℝ := alg3X inst y
(∀ j, 1 ≤ ∑ i ∈ inst.S j, x i) ∧
((∀ j, 0 ≤ y j) ∧ ∀ i : I, dualSum inst y i ≤ inst.c i * (1 + Real.log inst.d)) ∧
(∀ x'' : I → ℝ, (∀ i, 0 ≤ x'' i) → (∀ j, 1 ≤ ∑ i ∈ inst.S j, x'' i) →
∑ i, inst.c i * x i ≤ 2 * (1 + Real.log 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 * ∑ j, y j) := by sorry
end OnlinePrimalDual.Framework