  In [SIAM J. Optim., 2022], the authors introduced a new linear programming
(LP) relaxation for K-means clustering. In this paper, we further investigate
the theoretical properties of this relaxation. We focus on K-means clustering
with two clusters, which is an NP-hard problem. As evident from our numerical
experiments with both synthetic and real-world data sets, the proposed LP
relaxation is almost always tight; i.e. its optimal solution is feasible for
the original nonconvex problem. To better understand this unexpected behaviour,
we obtain sufficient conditions under which the LP relaxation is tight. We
further analyze the sufficient conditions when the input is generated according
to a popular stochastic model and obtain recovery guarantees for the LP
relaxation. Finally, we construct a family of inputs for which the LP
relaxation is never tight.
