Timezone: »

 
Oral
A Better k-means++ Algorithm via Local Search
Silvio Lattanzi · Christian Sohler

Thu Jun 13 12:00 PM -- 12:05 PM (PDT) @ Room 103

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.

Author Information

Silvio Lattanzi (Google Zurich)
Christian Sohler (Google)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors