Book chapter
On Metric Clustering to Minimize the Sum of Radii
Algorithm Theory – SWAT 2008, pp.282-293
Lecture Notes in Computer Science, Springer Berlin Heidelberg
2008
DOI: 10.1007/978-3-540-69903-3_26
Abstract
Given an n-point metric (P,d) and an integer k > 0, we consider the problem of covering P by k balls so as to minimize the sum of the radii of the balls. We present a randomized algorithm that runs in nO(logn ·logΔ) time and returns with high probability the optimal solution. Here, Δ is the ratio between the maximum and minimum interpoint distances in the metric space. We also show that the problem is NP-hard, even in metrics induced by weighted planar graphs and in metrics of constant doubling dimension.
Details
- Title: Subtitle
- On Metric Clustering to Minimize the Sum of Radii
- Creators
- Matt Gibson - University of IowaGaurav Kanade - University of IowaErik Krohn - University of IowaImran A. Pirwani - University of IowaKasturi Varadarajan - University of Iowa
- Resource Type
- Book chapter
- Publication Details
- Algorithm Theory – SWAT 2008, pp.282-293
- Publisher
- Springer Berlin Heidelberg; Berlin, Heidelberg
- Series
- Lecture Notes in Computer Science
- DOI
- 10.1007/978-3-540-69903-3_26
- eISSN
- 1611-3349
- ISSN
- 0302-9743
- Language
- English
- Date published
- 2008
- Academic Unit
- Computer Science
- Record Identifier
- 9984259483102771
Metrics
14 Record Views