Near-linear Time Approximation Schemes for Clustering in Doubling Metrics

DOI10.1145/3477541zbMath1499.68362arXiv1812.08664OpenAlexW3208255119MaRDI QIDQ5056433

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

approximation schemeEuclidean spacesdoubling dimension\(k\)-means\(k\)-median

Mathematics Subject Classification ID

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

Related Items (3)

Better guarantees for \(k\)-median with service installation costs ⋮ Generalized \(k\)-center: distinguishing doubling and highway dimension ⋮ Approximation algorithms for fair \(k\)-median problem without fairness violation

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