Cluster LP rounding for triangles with three positive edges
ProvedDualSepClusterLP.threePositiveTriangleEndpointsapproximation-algorithmscluster-lpcorrelation-clustering
For a triangle with three positive edges, take arbitrary pair masses in the unit interval for which the interval of feasible triple masses is nonempty. At both its endpoints, the sum over pivots of the released budget minus the expected disagreement and covariance correction is nonnegative. The rounding budgets use the exact value .
Preamble
import Definitions.Def_DualSepClusterLP_RoundingAnalysis
Formal statement
namespace DualSepClusterLP
theorem threePositiveTriangleEndpoints (x y z : ℝ)
(hx : x ∈ Set.Icc (0:ℝ) 1) (hy : y ∈ Set.Icc (0:ℝ) 1)
(hz : z ∈ Set.Icc (0:ℝ) 1) (hn : tripleLower x y z ≤ tripleUpper x y z) :
0 ≤ signedTriangleSurplus true true true x y z (tripleLower x y z) ∧
0 ≤ signedTriangleSurplus true true true x y z (tripleUpper x y z) := by sorry
end DualSepClusterLPSource
David García-Soriano and Antoine Schohn, Approximate Dual Separation for the Cluster LP, Lemma 7.3 and Appendix C, https://arxiv.org/abs/2607.27829.