Recovery threshold conjecture for the K-means linear-programming relaxation

Let $m \geq 2$, and suppose that the points are generated according to the stochastic block model with equal-size clusters. Let $\Delta$ denote the cluster separation parameter, and let Problem~ be the linear-programming relaxation used by Algorithm~\cert.

Recovery-threshold conjecture. If $\Delta > 2.14$, then Problem~ recovers the planted clusters with high probability.

If true, this recovery guarantee would improve on that of the semidefinite-programming relaxation for $m \leq 202$. The recovery threshold for K-means clustering under the stochastic block model remains open for $m>1$.