Theorem 1.3 — deterministic cluster-LP rounding at
ProvedDualSepClusterLP.deterministicRoundingapproximation-algorithmscluster-lpcorrelation-clustering
From an explicitly represented feasible rational cluster-LP solution, a deterministic polynomial-time algorithm returns a clustering with cost at most times the supplied objective value.
Preamble
import Mathlib import Mathlib.Computability.TuringMachine.Computable import Definitions.Def_DualSepClusterLP_SparseInput
Formal statement
namespace DualSepClusterLP
/-- Theorem 1.3 and Proposition F.1 for an explicitly supplied feasible rational support.
The step bound is polynomial in the full bit length of the graph and LP input. -/
theorem deterministicRounding :
∃ (M : Turing.TM2ComputableAux Bool Bool) (A b : ℕ),
(∀ k, Finite (M.tm.Γ k)) ∧
∀ (n : ℕ) (G : Graph n) (L : SparseWeights n), ValidSupport L →
∃ C : Clustering n,
Nonempty (Turing.TM2OutputsInTime M.tm
((roundingInput G L).map M.inputAlphabet.symm)
(some ((partitionOutput C).map M.outputAlphabet.symm))
(A * ((roundingInput G L).length + 1)^b)) ∧
(disagreements G C : ℝ) ≤ (2773 / 2000 : ℝ) *
primalValue G (fun S => (weightAt L S : ℝ)) := by sorry
end DualSepClusterLP
Source
David García-Soriano and Antoine Schohn, Approximate Dual Separation for the Cluster LP, STOC 2027 paper #79, §1, Theorem 1.3 and Appendix F, Proposition F.1. https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/79.pdf
Read-back
What the Lean code literally says, in plain math · Codex (GPT-6)
One deterministic finite-alphabet machine rounds every valid explicit list to a partition whose disagreement count is at most 2773/2000 times the supplied fractional objective. Time is polynomial in the full encoded input length. The supplied list may be exponentially large in n, and the assertion does not produce it.
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.