Near-linear Time Approximation Schemes for Clustering in Doubling Metrics

DOI10.1145/3477541MaRDI QIDQ5056433zbMATH OpenOpenAlexFDO

Authors Vincent Cohen-Addad, Andreas Emil Feldmann, David Saulpic

Publication date 8 December 2022

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1812.08664

zbMATH Keywords

\(k\)-means\(k\)-medianapproximation schemedoubling dimensionEuclidean spaces

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Discrete location and assignment (90B80)

Abstract: We consider the classic Facility Location, $k$-Median, and $k$-Means problems in metric spaces of doubling dimension $d$. We give nearly linear-time approximation schemes for each problem. The complexity of our algorithms is $2^{(log(1/eps)/eps{)}^{O(d^2)}}nlo{g}^{4}n+2^{O(d)}nlo{g}^{9}n$, making a significant improvement over the state-of-the-art algorithms which run in time $n^{(d/eps{)}^{O(d)}}$. 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.

Recommendations

• Local search yields a PTAS for \(k\)-means in doubling metrics
• Linear-time approximation schemes for clustering problems in any dimensions
• Approximation schemes for clustering with outliers
• Approximation schemes for clustering with outliers
• Approximation schemes for clustering problems

Cited in

(17)

• Better guarantees for \(k\)-median with service installation costs
• Clustering for metric and nonmetric distance measures
• Linear-time approximation schemes for clustering problems in any dimensions
• Approximation schemes for clustering with outliers
• Local search yields a PTAS for \(k\)-means in doubling metrics
• Approximation schemes for clustering with outliers
• Approximation Schemes for Capacitated Clustering in Doubling Metrics
• Generalized \(k\)-center: distinguishing doubling and highway dimension
• Approximation algorithms for fair k-median problem without fairness violation
• A PTAS framework for clustering problems in doubling metrics
• Generalized k-center: distinguishing doubling and highway dimension
• Improved approximation algorithm for individual fairness k-median
• Better guarantees for individual fairness k-median
• Faster approximation schemes for (constrained) k-means with outliers
• On connections between k-coloring and Euclidean k-means
• A QPTAS for facility location on unit disk graphs
• Clustering in varying metrics

This page was built for publication: Near-linear Time Approximation Schemes for Clustering in Doubling Metrics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5056433)