On Metric Clustering to Minimize the Sum of Radii

DOI10.1007/978-3-540-69903-3_26zbMATH Open1155.68570OpenAlexW1496527880MaRDI QIDQ3512466FDOQ3512466

Authors Gaurav Kanade, Imran A. Pirwani, Matt Gibson, Erik Krohn, Kasturi Varadarajan

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\)-clustering\(k\)-coverdoubling metricmetric clusteringplanar metric

Mathematics Subject Classification ID

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

Recommendations

• On metric clustering to minimize the sum of radii
• On minimum sum of radii and diameters clustering
• On clustering to minimize the sum of radii
• Clustering to minimize the sum of cluster diameters
• On minimum sum of radii and diameters clustering

Cites work

• scientific article; zbMATH DE number 5764795 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 6469222 (Why is no real title available?)
• A Best Possible Heuristic for the k-Center Problem
• A randomized approximation scheme for metric MAX-CUT
• A tight bound on approximating arbitrary metrics by tree metrics
• Algorithms – ESA 2005
• An Algorithmic Approach to Network Location Problems. II: Thep-Medians
• Approximation algorithms for clustering to minimize the sum of diameters
• Clustering to minimize the sum of cluster diameters
• Minimum-cost coverage of point sets by disks
• Planar Formulae and Their Uses
• Polynomial time approximation schemes for base station coverage with minimum total radii

Cited in

(13)

• The Planar k-Means Problem is NP-Hard
• On minimum sum of radii and diameters clustering
• Approximate clustering via metric partitioning
• Approximating min-sum k -clustering in metric spaces
• Maximizing the sum of radii of disjoint balls or disks
• Dynamic clustering to minimize the sum of radii
• On metric clustering to minimize the sum of radii
• The planar \(k\)-means problem is NP-hard
• Dynamic clustering to minimize the sum of radii
• On minimum sum of radii and diameters clustering
• On clustering to minimize the sum of radii
• Shifting strategy for geometric graphs without geometry
• The structural clustering and analysis of metric based on granular space

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

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