Theorem 1.5 — must-link-only randomized (1.3865 + ε) approximation
OpenConstrainedCorrelationRepulsion.Main.Supplement.theorem_1_5approximationcorrelation-clusteringp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
For every fixed real , there is one finite randomized program running in polynomial time on every feasible complete unweighted instance with must-links only. Every supported output satisfies all must-links and
The vertex count, signs and must-link components are unrestricted, including empty and singleton inputs. The polynomial constants and program may depend on and are chosen before all inputs. This is unconditional algorithm existence; it assumes no unconstrained approximation algorithm as a hypothesis. The existing true-twin and expansion constructions preserve empty , allowing the cited unconstrained algorithm to be used with accuracy and transfer slack .
Differences from the source:
- encoding: randomized polynomial-time (1.3865 + ε)-approximation with must-links only → uniform published fair-coin bit-cost program guarantee on H-empty inputs, with 1.3865 = 2773/2000 exactly; reason: this states the same expected objective ratio and hard feasibility on every output; padding max(2,n) includes empty and singleton inputs
Preamble
import Definitions.Def_ConstrainedCorrelationRepulsion_Main_Supplement_MustLinks
Formal statement
namespace ConstrainedCorrelationRepulsion.Main.Supplement
/-- Theorem 1.5, printed p.16 / PDF p.17: the final unconditional existence result,
not a transfer theorem with the external unconstrained algorithm assumed. -/
theorem theorem_1_5 (epsilon : ℝ) (hepsilon : 0 < epsilon) :
MustLinkApproximation ((2773 : ℝ)/2000 + epsilon) := by sorry
end ConstrainedCorrelationRepulsion.Main.Supplement
Source
Yixin Cao, Ying Xu, STOC 2027 submission #869 (October 2026), Theorem 1.5, printed p.16 (PDF p.17), also announced printed p.2 (PDF p.3)