On Metric Clustering to Minimize the Sum of Radii

DOI10.1007/978-3-540-69903-3_26zbMath1155.68570MaRDI QIDQ3512466

Gaurav Kanade, Imran A. Pirwani, Kasturi R. Varadarajan, Matthew R. Gibson, Erik A. Krohn

Publication date: 15 July 2008

Published in: Algorithm Theory – SWAT 2008 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-69903-3_26

zbMATH Keywords

clustering; \(k\)-cover; \(k\)-clustering; doubling metric; metric clustering; planar metric

Mathematics Subject Classification ID

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W20: Randomized algorithms

Related Items

The planar \(k\)-means problem is NP-hard, Shifting strategy for geometric graphs without geometry, On minimum sum of radii and diameters clustering, The structural clustering and analysis of metric based on granular space, The Planar k-Means Problem is NP-Hard

Cites Work

• A randomized approximation scheme for metric MAX-CUT
• Clustering to minimize the sum of cluster diameters
• Polynomial time approximation schemes for base station coverage with minimum total radii
• A Best Possible Heuristic for the k-Center Problem
• An Algorithmic Approach to Network Location Problems. II: Thep-Medians
• Planar Formulae and Their Uses
• Algorithms – ESA 2005
• A tight bound on approximating arbitrary metrics by tree metrics
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item