Abstract
When do convex relaxations return integer solutions? In this talk, I will discuss several instances of discrete optimization problems where, for a suitable distribution on inputs, LP and SDP relaxations produce integer solutions with high probability. This phenomenon has been studied in the context of LP decoding, sparse recovery, stochastic block models and so on. I will also mention some recent results for clustering problems: when points are drawn from a distribution over k sufficiently separated clusters, the well known k-median relaxation and a (not so well known) SDP relaxation for k-means exactly recover the clusters.