Near-Linear Time Approximations Schemes for Clustering in Doubling Metrics

Vincent Cohen-Addad, Andreas Emil Feldmann, David Saulpic

Type: Preprint

Publication Date: 2019-11-01

Citations: 21

DOI: https://doi.org/10.1109/focs.2019.00041

Abstract

We consider the classic Facility Location, k-Median, and k-Means problems in metric spaces of constant doubling dimension. We give the first nearly linear-time approximation schemes for each problem, making a significant improvement over the state-of-the-art algorithms. Moreover, we show how to extend the techniques used to get the first efficient approximation schemes for the problems of prize-collecting k-Medians and k-Means, and efficient bicriteria approximation schemes for k-Medians with outliers, k-Means with outliers and k-Center.

Locations

HAL (Le Centre pour la Communication Scientifique Directe) - View - PDF
White Rose Research Online (University of Leeds) - View - PDF

Similar Works

Action	Title	Year	Authors
+	Near-linear Time Approximation Schemes for Clustering in Doubling Metrics	2021	Vincent Cohen-Addad Andreas Emil Feldmann David Saulpic
+	Near-Linear Time Approximation Schemes for Clustering in Doubling Metrics	2018	Vincent Cohen-Addad Andreas Emil Feldmann David Saulpic
+	Near-Linear Time Approximation Schemes for Clustering in Doubling Metrics.	2018	Vincent Cohen-Addad Andreas Emil Feldmann David Saulpic
+	Approximation Schemes for Clustering with Outliers	2017	Zachary Friggstad Kamyar Khodamoradi Mohsen Rezapour Mohammad R. Salavatipour
+ PDF Chat	Approximation Schemes for Clustering with Outliers	2018	Zachary Friggstad Kamyar Khodamoradi Mohsen Rezapour Mohammad R. Salavatipour
+ PDF Chat	Approximation Schemes for Clustering with Outliers	2019	Zachary Friggstad Kamyar Khodamoradi Mohsen Rezapour Mohammad R. Salavatipour
+	Approximation Schemes for Capacitated Clustering in Doubling Metrics	2018	Vincent Cohen-Addad
+	Approximation Schemes for Capacitated Clustering in Doubling Metrics	2018	Vincent Cohen-Addad
+	Parameterized Approximation Schemes for Clustering with General Norm Objectives	2023	Fateme Abbasi Sandip Banerjee Jarosław Byrka Parinya Chalermsook Ameet Gadekar Kamyar Khodamoradi Dániel Marx Roohani Sharma Joachim Spoerhase
+ PDF Chat	Approximation Schemes for Capacitated Clustering in Doubling Metrics	2019	Vincent Cohen-Addad
+	Local Search Yields a PTAS for k-Means in Doubling Metrics	2016	Zachary Friggstad Mohsen Rezapour Mohammad R. Salavatipour
+	Moderate Dimension Reduction for $k$-Center Clustering	2023	Shaofeng H. -C. Jiang Robert Krauthgamer Shay Sapir
+ PDF Chat	A Subquadratic Time Approximation Algorithm for Individually Fair k-Center	2024	Matthijs Ebbens Nicole Funk Jan Höckendorff Christian Sohler Vera Weil
+	Local Search Yields a PTAS for k-Means in Doubling Metrics	2016	Zachary Friggstad Mohsen Rezapour Mohammad R. Salavatipour
+	Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering	2021	Shyam Narayanan Sandeep Silwal Piotr Indyk Or Zamir
+	Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering	2021	Shyam Narayanan Sandeep Silwal Piotr Indyk Or Zamir
+	Approximation Algorithms for Continuous Clustering and Facility Location Problems	2022	Deeparnab Chakrabarty Maryam Negahbani Ankita Sarkar
+	Accurate MapReduce Algorithms for $k$-median and $k$-means in General Metric Spaces	2019	Alessio Mazzetto Andrea Pietracaprina Geppino Pucci
+	FPT Approximations for Capacitated/Fair Clustering with Outliers	2023	Rajni Dabas Neelima Gupta Tanmay Inamdar
+	On Coresets for Clustering in Small Dimensional Euclidean Spaces	2023	Lingxiao Huang Ruiyuan Huang Zengfeng Huang Xuan Wu

Works That Cite This (12)

Action	Title	Year	Authors
+ PDF Chat	A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms	2020	Andreas Emil Feldmann C. S. Karthik Euiwoong Lee Pasin Manurangsi
+	Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metrics	2021	Vincent Cohen-Addad C. S. Karthik Euiwoong Lee
+	A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms	2020	Andreas Emil Feldmann C. S. Karthik Euiwoong Lee Pasin Manurangsi
+ PDF Chat	Johnson Coverage Hypothesis: Inapproximability of <i>k</i>-means and <i>k</i>-median in <i>ℓ<sub>p</sub></i>-metrics	2022	Vincent Cohen-Addad C. S. Karthik Euiwoong Lee
+ PDF Chat	Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to <i>k</i>-Median	2023	Vincent Cohen-Addad Viallat Fabrizio Grandoni Euiwoong Lee Chris Schwiegelshohn
+	Clustering under Perturbation Stability in Near-Linear Time	2020	Pankaj K. Agarwal Hsien-Chih Chang Kamesh Munagala Erin Taylor Emo Welzl
+	Approximation Schemes for Capacitated Clustering in Doubling Metrics	2018	Vincent Cohen-Addad
+ PDF Chat	Almost Tight Approximation Algorithms for Explainable Clustering	2022	Hossein Esfandiari Vahab Mirrokni Shyam Narayanan
+	A local search algorithm for k-means with outliers	2021	Zhen Zhang Qilong Feng Junyu Huang Yutian Guo Jinhui Xu Jianxin Wang
+	Almost-linear <i>ε</i> -emulators for planar graphs	2022	Hsien-Chih Chang Robert Krauthgamer Zihan Tan

Works Cited by This (16)

Action	Title	Year	Authors
+	Fast, precise and dynamic distance queries	2011	Yair Bartal Lee-Ad Gottlieb Tsvi Kopelowitz Moshe Lewenstein Liam Roditty
+ PDF Chat	Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams	2015	Dániel Marx Michał Pilipczuk
+	The Hardness of Approximation of Euclidean k-means	2015	Pranjal Awasthi Moses Charikar Ravishankar Krishnaswamy Ali Kemal Sinop
+	Fast Construction of Nets in Low-Dimensional Metrics and Their Applications	2006	Sariel Har-Peled Manor Mendel
+ PDF Chat	Random Projection Trees for Vector Quantization	2009	Sanjoy Dasgupta Yoav Freund
+ PDF Chat	Bounded geometries, fractals, and low-distortion embeddings	2004	Anupam Gupta Robert Krauthgamer J.R. Lee
+ 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	On the Local Structure of Stable Clustering Instances	2017	Vincent Cohen-Addad Chris Schwiegelshohn
+ PDF Chat	Constant approximation for k-median and k-means with outliers via iterative rounding	2018	Ravishankar Krishnaswamy Li Shi Sai Sandeep
+	Fast, precise and dynamic distance queries	2011	Yair Bartal Lee-Ad Gottlieb Tsvi Kopelowitz Moshe Lewenstein Liam Roditty