Cluster LP rounding for triangles with two positive edges and one negative edge
ProvedDualSepClusterLP.twoPositiveTriangleEndpointsapproximation-algorithmscluster-lpcorrelation-clustering
For a triangle with two positive edges and one negative edge, 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 twoPositiveTriangleEndpoints (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 false x y z (tripleLower x y z) ∧
0 ≤ signedTriangleSurplus true true false 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.