On Metric Clustering to Minimize the Sum of Radii

DOI10.1007/978-3-540-69903-3_26zbMath1155.68570OpenAlexW1496527880MaRDI 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\)-clusteringdoubling metricmetric clusteringplanar metric

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

Related Items (7)

Dynamic clustering to minimize the sum of radii ⋮ 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 ⋮ Unnamed Item

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

This page was built for publication: On Metric Clustering to Minimize the Sum of Radii