Timezone: »
Oral
A Better k-means++ Algorithm via Local Search
Silvio Lattanzi · Christian Sohler
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)
-
2019 Poster: A Better k-means++ Algorithm via Local Search »
Fri. Jun 14th 01:30 -- 04:00 AM Room Pacific Ballroom #193
More from the Same Authors
-
2023 Poster: Speeding Up Bellman Ford via Minimum Violation Permutations »
Silvio Lattanzi · Ola Svensson · Sergei Vassilvitskii -
2023 Poster: Fully Dynamic Submodular Maximization over Matroids »
PAUL DUETTING · Federico Fusco · Silvio Lattanzi · Ashkan Norouzi-Fard · Morteza Zadimoghaddam -
2022 Poster: Deletion Robust Submodular Maximization over Matroids »
PAUL DUETTING · Federico Fusco · Silvio Lattanzi · Ashkan Norouzi-Fard · Morteza Zadimoghaddam -
2022 Poster: Online and Consistent Correlation Clustering »
Vincent Cohen-Addad · Silvio Lattanzi · Andreas Maggiori · Nikos Parotsidis -
2022 Oral: Deletion Robust Submodular Maximization over Matroids »
PAUL DUETTING · Federico Fusco · Silvio Lattanzi · Ashkan Norouzi-Fard · Morteza Zadimoghaddam -
2022 Spotlight: Online and Consistent Correlation Clustering »
Vincent Cohen-Addad · Silvio Lattanzi · Andreas Maggiori · Nikos Parotsidis -
2021 Poster: Correlation Clustering in Constant Many Parallel Rounds »
Vincent Cohen-Addad · Silvio Lattanzi · Slobodan Mitrović · Ashkan Norouzi-Fard · Nikos Parotsidis · Jakub Tarnawski -
2021 Oral: Correlation Clustering in Constant Many Parallel Rounds »
Vincent Cohen-Addad · Silvio Lattanzi · Slobodan Mitrović · Ashkan Norouzi-Fard · Nikos Parotsidis · Jakub Tarnawski -
2019 Poster: Improved Parallel Algorithms for Density-Based Network Clustering »
Mohsen Ghaffari · Silvio Lattanzi · Slobodan Mitrović -
2019 Poster: Submodular Streaming in All Its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity »
Ehsan Kazemi · Marko Mitrovic · Morteza Zadimoghaddam · Silvio Lattanzi · Amin Karbasi -
2019 Oral: Submodular Streaming in All Its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity »
Ehsan Kazemi · Marko Mitrovic · Morteza Zadimoghaddam · Silvio Lattanzi · Amin Karbasi -
2019 Oral: Improved Parallel Algorithms for Density-Based Network Clustering »
Mohsen Ghaffari · Silvio Lattanzi · Slobodan Mitrović -
2018 Poster: Parallel and Streaming Algorithms for K-Core Decomposition »
Hossein Esfandiari · Silvio Lattanzi · Vahab Mirrokni -
2018 Oral: Parallel and Streaming Algorithms for K-Core Decomposition »
Hossein Esfandiari · Silvio Lattanzi · Vahab Mirrokni -
2017 Poster: Consistent k-Clustering »
Silvio Lattanzi · Sergei Vassilvitskii -
2017 Talk: Consistent k-Clustering »
Silvio Lattanzi · Sergei Vassilvitskii