Correctness of the two executable conditional-expectation rounders
ProvedDualSepClusterLP.sparseRounderTraceCorrectapproximation-algorithmscluster-lpcorrelation-clustering
For a feasible explicit rational cluster LP solution satisfying the clock and pivot step bounds, the executable word function outputs the cheaper of two partitions. Every round of each partition covers its disagreements from the corresponding released edge budgets.
Preamble
import Definitions.Def_DualSepClusterLP_SparseRounder
Formal statement
namespace DualSepClusterLP
theorem sparseRounderTraceCorrect {n : ℕ} (G : Graph n) (L : SparseWeights n)
(hL : ValidSupport L) (hc : ClockStepOK G (fun S => (weightAt L S : ℝ)))
(hp : PivotStepOK G (fun S => (weightAt L S : ℝ))) :
∃ C P : Clustering n,
RoundTraceOK G C (fun S => (weightAt L S : ℝ)) clusterEdgeBudget ∧
RoundTraceOK G P (fun S => (weightAt L S : ℝ)) pivotEdgeBudget ∧
RoundWire.output (roundingInput G L) =
partitionOutput (if disagreements G C ≤ disagreements G P then C else P) := by sorry
end DualSepClusterLPSource
David García-Soriano and Antoine Schohn, Approximate Dual Separation for the Cluster LP, Appendix F (conditional-expectation rounding), https://arxiv.org/abs/2607.27829.