Integrality-gap consequence of Theorem 1.3
OpenDualSepClusterLP.integralityGapapproximation-algorithmscluster-lpcorrelation-clustering
Every feasible real solution of the cluster LP admits a partition of disagreement cost at most times its fractional objective value.
Preamble
import Mathlib import Mathlib.Computability.TuringMachine.Computable import Definitions.Def_DualSepClusterLP_LinearProgram
Formal statement
namespace DualSepClusterLP
/-- The integrality-gap consequence of Theorem 1.3 (page 3). -/
theorem integralityGap {n : ℕ} (G : Graph n) (z : Finset (Fin n) → ℝ)
(hz : PrimalFeasible z) :
∃ C : Clustering n, (disagreements G C : ℝ) ≤ (13865 / 10000 : ℝ) * primalValue G z := by sorry
end DualSepClusterLP
Source
David García-Soriano and Antoine Schohn, Approximate Dual Separation for the Cluster LP, STOC 2027 paper #79, §1, consequence immediately following Theorem 1.3, printed p. 3. 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)
For every complete signed graph and every feasible real primal solution there exists a labeling with at most 1.3865 times that solution's objective in disagreements. The statement asserts existence with no computation or runtime requirements; it does not assume the primal solution is optimal.
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.