  We introduce the ratio-cut polytope defined as the convex hull of ratio-cut
vectors corresponding to all partitions of $n$ points in $\mathbb R^m$ into at
most $K$ clusters. This polytope is closely related to the convex hull of the
feasible region of a number of clustering problems such as K-means clustering
and spectral clustering. We study the facial structure of the ratio-cut
polytope and derive several types of facet-defining inequalities. We then
consider the problem of K-means clustering and introduce a novel linear
programming (LP) relaxation for it. Subsequently, we focus on the case of two
clusters and derive sufficient conditions under which the proposed LP
relaxation recovers the underlying clusters exactly. Namely, we consider the
stochastic ball model, a popular generative model for K-means clustering, and
we show that if the separation distance between cluster centers satisfies
$\Delta > 1+\sqrt 3$, then the LP relaxation recovers the planted clusters with
high probability. This is a major improvement over the only existing recovery
guarantee for an LP relaxation of K-means clustering stating that recovery is
possible with high probability if and only if $\Delta > 4$. Our numerical
experiments indicate that the proposed LP relaxation significantly outperforms
a popular semidefinite programming relaxation in recovering the planted
clusters.
