Corollary 2.4 — sparse primal and dual solutions for the cluster LP
ProvedDualSepClusterLP.primalDualApproximationThe deterministic solver returns exactly feasible signed rational prices and an explicitly supported feasible rational primal vector. At accuracy their objectives bound the fractional optimum from below and above within a factor on each side. The support is polynomial in and the running time is .
import Mathlib import Mathlib.Computability.TuringMachine.Computable import Definitions.Def_DualSepClusterLP_SparseInput
namespace DualSepClusterLP
/-- Corollary 2.4 at accuracy 1/(t+1). The LP optimum is the infimum of the
objectives of all feasible real primal vectors. The output contains the explicit
rational primal list, followed by the signed rational dual prices. -/
theorem primalDualApproximation :
∃ (M : Turing.TM2ComputableAux Bool Bool) (A a b D d : ℕ),
(∀ k, Finite (M.tm.Γ k)) ∧
∀ (t n : ℕ) (G : Graph n), ∃ (L : SparseWeights n) (q : Fin n → ℚ),
Nonempty (Turing.TM2OutputsInTime M.tm
((graphInput t G).map M.inputAlphabet.symm)
(some ((roundingInput G L ++ pricesBits q).map M.outputAlphabet.symm))
(2 ^ (A * (t+1)^a) * (n+1)^b)) ∧
ValidSupport L ∧ L.length ≤ D * (n+1)^d ∧
DualFeasible G (fun i => (q i : ℝ)) ∧
let opt : ℝ := sInf {v : ℝ | ∃ z : Finset (Fin n) → ℝ, PrimalFeasible z ∧ primalValue G z = v}
let factor : ℝ := 1 + 1 / ((t : ℝ) + 1)
opt ≤ factor * ∑ i : Fin n, (q i : ℝ) ∧
primalValue G (fun S => (weightAt L S : ℝ)) ≤ factor * opt := by sorry
end DualSepClusterLP
Read-back
What the Lean code literally says, in plain math · Codex (GPT-6)
One deterministic finite-alphabet machine and fixed natural constants A,a,b,D,d work for every accuracy index t, graph size n and graph. In time 2^{A(t+1)^a}(n+1)^b it outputs a valid primal list of length at most D(n+1)^d and feasible signed rational prices. If OPT is the infimum of all feasible real primal objectives and f=1+1/(t+1), then OPT is at most f times the sum of the prices and the returned primal value is at most f times OPT. The direct primal-to-dual factor of these two inequalities is f². No integral clustering is promised.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.