On metric clustering to minimize the sum of radii

DOI10.1007/s00453-009-9282-7zbMath1201.68152OpenAlexW4255110400MaRDI QIDQ970610

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

Publication date: 19 May 2010

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-009-9282-7

zbMATH Keywords

clusteringapproximation algorithmpolynomial time

Mathematics Subject Classification ID

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

Related Items (6)

Unnamed Item ⋮ Online sum-radii clustering ⋮ On minimum sum of radii and diameters clustering ⋮ MULTI COVER OF A POLYGON MINIMIZING THE SUM OF AREAS ⋮ Multi Cover of a Polygon Minimizing the Sum of Areas ⋮ Maximizing the ratio of cluster split to cluster diameter without and with cardinality constraints

Cites Work

• Graph clustering
• 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
• Competitive algorithms for server problems
• 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