The ratio-cut polytope and K-means clustering

Antonio De Rosa, Aida Khajavirad

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 p…