Noisy, Greedy and Not So Greedy k-means++

Anup Bhattacharya, Jan Eube, Heiko Röglin, Melanie Schmidt

Type: Preprint

Publication Date: 2019-01-01

Citations: 6

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

View Publication

Locations

arXiv (Cornell University) - View
DataCite API - View

Similar Works

Action	Title	Year	Authors
+	Noisy k-means++ Revisited	2023	Christoph Grunau Ahmet Alper Özüdoğru Václav Rozhoň
+	A Nearly Tight Analysis of Greedy k-means++	2022	Christoph Grunau Ahmet Alper Özüdoğru Václav Rozhoň Jakub Tětek
+ PDF Chat	A Nearly Tight Analysis of Greedy k-means++	2023	Christoph Grunau Ahmet Alper Özüdoğru Václav Rozhoň Jakub Tětek
+	Improved Outlier Robust Seeding for k-means	2023	Amit Deshpande Rameshwar Pratap
+	A simple D^2-sampling based PTAS for k-means and other Clustering Problems	2012	Ragesh Jaiswal Amit Kumar Sandeep Sen
+	Fast and Accurate $k$-means++ via Rejection Sampling	2020	Vincent Cohen-Addad Silvio Lattanzi Ashkan Norouzi-Fard Christian Sohler Ola Svensson
+	Fast and Accurate $k$-means++ via Rejection Sampling	2020	Vincent Cohen-Addad Silvio Lattanzi Ashkan Norouzi-Fard Christian Sohler Ola Svensson
+	Fast and Accurate $k$-means++ via Rejection Sampling	2020	Vincent Cohen-Addad Silvio Lattanzi Ashkan Norouzi-Fard Christian Sohler Ola Svensson
+ PDF Chat	A New Rejection Sampling Approach to $k$-$\mathtt{means}$++ With Improved Trade-Offs	2025	Poojan Shah Sanjay Agrawal Ragesh Jaiswal
+	Adapting $k$-means algorithms for outliers	2020	Christoph Grunau Václav Rozhoň
+	A bad 2-dimensional instance for k-means++	2013	Ragesh Jaiswal Prachi Jain Saumya Yadav
+	A bad 2-dimensional instance for k-means++	2013	Ragesh Jaiswal Prachi Jain Saumya Yadav
+	Adapting k-means algorithms for outliers.	2020	Christoph Grunau Václav Rozhoň
+	A Constant-Factor Bi-Criteria Approximation Guarantee for $k$-means++	2016	Dennis Wei
+	k-means++: few more steps yield constant approximation	2020	Davin Choo Christoph Grunau Julian Portmann Václav Rozhoň
+	A tight lower bound instance for k-means++ in constant dimension	2014	Anup Bhattacharya Ragesh Jaiswal Nir Ailon
+	On Sampling Based Algorithms for k-Means.	2020	Anup Bhattacharya Dishant Goyal Ragesh Jaiswal Amit Kumar
+	Fast Noise Removal for $k$-Means Clustering	2020	Sungjin Im Mahshid Montazer Qaem Benjamin Moseley Xiaorui Sun Rudy Zhou
+	Provably noise-robust, regularised $k$-means clustering	2017	Shrinu Kushagra Nicole McNabb Yaoliang Yu Shai Ben-David
+	No-substitution k-means Clustering with Adversarial Order	2020	Robi Bhattacharjee Michal Moshkovitz

Works That Cite This (5)

Action	Title	Year	Authors
+	Simple and sharp analysis of k-means\|\|	2020	Václav Rozhoň
+	Fast and Accurate $k$-means++ via Rejection Sampling	2020	Vincent Cohen-Addad Silvio Lattanzi Ashkan Norouzi-Fard Christian Sohler Ola Svensson
+ PDF Chat	A Nearly Tight Analysis of Greedy k-means++	2023	Christoph Grunau Ahmet Alper Özüdoğru Václav Rozhoň Jakub Tětek
+	Adapting k-means algorithms for outliers.	2020	Christoph Grunau Václav Rozhoň
+ 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 (5)

Action	Title	Year	Authors
+	A unified framework for approximating and clustering data	2011	Dan Feldman Michael Langberg
+ PDF Chat	A comparative study of efficient initialization methods for the k-means clustering algorithm	2012	M. Emre Celebi Hassan A. Kingravi Patricio A. Vela
+ PDF Chat	Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms	2017	Sara Ahmadian Ashkan Norouzi-Fard Ola Svensson Justin Ward
+ PDF Chat	Local Search Yields a PTAS for $k$-Means in Doubling Metrics	2019	Zachary Friggstad Mohsen Rezapour Mohammad R. Salavatipour
+ PDF Chat	Improved and simplified inapproximability for k-means	2016	Euiwoong Lee Melanie Schmidt John C. Wright