k-means++: few more steps yield constant approximation

Davin Choo, Christoph Grunau, Julian Portmann, Václav Rozhoň

Type: Preprint

Publication Date: 2020-01-01

Citations: 5

DOI: https://doi.org/10.48550/arxiv.2002.07784

View Publication

Locations

arXiv (Cornell University) - View
DataCite API - View

Similar Works

Action	Title	Year	Authors
+ PDF Chat	A Nearly Tight Analysis of Greedy k-means++	2023	Christoph Grunau Ahmet Alper Özüdoğru Václav Rozhoň Jakub Tětek
+	A Nearly Tight Analysis of Greedy k-means++	2022	Christoph Grunau Ahmet Alper Özüdoğru Václav Rozhoň Jakub Tětek
+ PDF Chat	Local Search Yields a PTAS for $k$-Means in Doubling Metrics	2019	Zachary Friggstad Mohsen Rezapour Mohammad R. Salavatipour
+ PDF Chat	Local Search Yields a PTAS for k-Means in Doubling Metrics	2016	Zachary Friggstad Mohsen Rezapour Mohammad R. Salavatipour
+ PDF Chat	Local Search k-means++ with Foresight	2024	Theo Conrads Lukas Drexler Joshua Könen Daniel R. Schmidt Melanie Schmidt
+	Noisy k-means++ Revisited	2023	Christoph Grunau Ahmet Alper Özüdoğru Václav Rozhoň
+	Exact Acceleration of K-Means++ and K-Means\|\|	2021	Edward Raff
+	Theoretical Analysis of the $k$-Means Algorithm - A Survey	2016	Johannes Blömer Christiane Lammersen Melanie Schmidt Christian Sohler
+	Theoretical Analysis of the $k$-Means Algorithm - A Survey	2016	Johannes Blömer Christiane Lammersen Melanie Schmidt Christian Sohler
+ PDF Chat	Almost-linear Time Approximation Algorithm to Euclidean $k$-median and $k$-means	2024	Max Dupré la Tour David Saulpic
+	How Fast Is k-Means?	2003	Sanjoy Dasgupta
+ PDF Chat	Faster K-Means Cluster Estimation	2017	Siddhesh Khandelwal Amit Awekar
+	Multi-Swap $k$-Means++	2023	Lorenzo Beretta Vincent Cohen-Addad Silvio Lattanzi Nikos Parotsidis
+	Exact Acceleration of K-Means++ and K-Means$\\|$	2021	Edward Raff
+	Noisy, Greedy and Not So Greedy k-means++	2019	Anup Bhattacharya Jan Eube Heiko Röglin Melanie Schmidt
+	Adapting $k$-means algorithms for outliers	2020	Christoph Grunau Václav Rozhoň
+	Exact Acceleration of K-Means++ and K-Means$\\|$	2021	Edward Raff
+	Improved Guarantees for k-means++ and k-means++ Parallel	2020	Konstantin Makarychev A. Rama Mohan Reddy Liren Shan
+ PDF Chat	Theoretical Analysis of the k-Means Algorithm – A Survey	2016	Johannes Blömer Christiane Lammersen Melanie Schmidt Christian Sohler
+	Improved Smoothed Analysis of the k-Means Method	2008	Bodo Manthey Heiko Röglin

Works That Cite This (2)

Action	Title	Year	Authors
+ PDF Chat	A Nearly Tight Analysis of Greedy k-means++	2023	Christoph Grunau Ahmet Alper Özüdoğru Václav Rozhoň Jakub Tětek
+ PDF Chat	Low-Distortion Clustering with Ordinal and Limited Cardinal Information	2024	Jakob Burkhardt Ioannis Caragiannis Karl Fehrs Matteo Russo Chris Schwiegelshohn Sudarshan Shyam

Works Cited by This (0)

Action	Title	Year	Authors