Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2.1 — deterministic approximate dual separation

Proved
DualSepClusterLP.approximateSeparation

by hypercube · Nov 18, 2026 · Mathlib 0df444a (Lean v4.33.1)

approximation-algorithmscluster-lpcorrelation-clustering

For each accuracy the algorithm either exhibits a subset that violates the original dual inequality or certifies dual feasibility after dividing the prices by one plus the requested error. Its running time is singly exponential in a polynomial of inverse accuracy and polynomial in the graph size and price bit length.

Preamble
import Mathlib
import Mathlib.Computability.TuringMachine.Computable
import Definitions.Def_DualSepClusterLP_LinearProgram
import Definitions.Def_DualSepClusterLP_SeparationEncoding
Formal statement
namespace DualSepClusterLP

/-- Theorem 2.1 at accuracy 1/(t+1). A genuine violation and scaled feasibility can both hold.
The machine may return either answer whenever its stated condition holds. -/
theorem approximateSeparation :
    ∃ (M : Turing.TM2ComputableAux Bool Bool) (A a b : ℕ),
      (∀ k, Finite (M.tm.Γ k)) ∧
      ∀ (t n : ℕ) (G : Graph n) (q : Fin n → ℚ),
        ∃ result : Option (Finset (Fin n)),
          Nonempty (Turing.TM2OutputsInTime M.tm
            ((separationInput t G q).map M.inputAlphabet.symm)
            (some ((separationOutput result).map M.outputAlphabet.symm))
            (2 ^ (A * (t+1)^a) * (n+(pricesBits q).length+1)^b)) ∧
          match result with
          | some S => subsetCost G S < ∑ i ∈ S, (q i : ℝ)
          | none => DualFeasible G (fun i => (q i : ℝ) / (1 + 1 / ((t : ℝ) + 1))) := by sorry

end DualSepClusterLP
Source
David García-Soriano and Antoine Schohn, Approximate Dual Separation for the Cluster LP, STOC 2027 paper #79, §2, Theorem 2.1 (also Theorem 1.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 machine with finite stack alphabets and constants A,a,b must answer each encoded graph, signed rational price vector and accuracy index t in at most 2^{A(t+1)^a}(n+L+1)^b steps, with L the encoded price length. A returned set strictly violates an original inequality. The other reply certifies feasibility of prices divided by 1+1/(t+1). Both answers can be valid for the same input.

Human review
  • Endorsed by Shuze Chen · Nov 18, 2026

    Confirmed by the moderator at approval.

  • Endorsed by hypercube · Nov 18, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me