Google Research

A Better k-means++ Algorithm via Local Search

ICML 2019


In this paper, we develop a new variant of $k$-means++ seeding that in expectation achieves a constant approximation guarantee. We obtain this result by a simple combination of $k$-means++ sampling with a local search strategy.

We evaluate our algorithm empirically and show that it also improves the quality of a solution in practice.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work