Our work improves on these results in several important ways. For the Bilu-Linial assumption, we show that for center-based clustering objectives (such as $k$-median or $k$-means) we can efficiently find the optimal clustering assuming only stability to constant-magnitude perturbations of the underlying metric. For the approximation assumption of Balcan et al., we relax their condition to require good behavior only for ``natural'' approximations of the objective: specifically, only approximations in which each point is assigned to its nearest center. We show that for the $k$-median objective, under the assumption that all such approximations yield the same partitioning, it is possible to obtain an optimal solution in polynomial time.
This is joint work with Pranjal Awasthi and Avrim Blum.