On the tightness of an SDP relaxation of k-means

Takayuki Iguchi, Dustin G. Mixon, Jesse Peterson +1

Recently, Awasthi et al. introduced an SDP relaxation of the $k$-means problem in ${\mathbb{R}}^m$. In this work, we consider a random model for the data points in which $k$ balls of…