Conference proceeding
On clustering to minimize the sum of radii
Proceedings of the nineteenth annual ACM-SIAM symposium on discrete algorithms, pp.819-825
SODA '08
01/20/2008
Abstract
Given a metric d defined on a set V of points (a metric space), we define the ball B( v, r ) centered at u ∈ V and having radius r ≥ 0 to be the set { q ∈ V/d(v, q) ≤ r }. In this work, we consider the problem of computing a minimum cost k -cover for a given set P ⊆ V of n points, where k > 0 is some given integer which is also part of the input. For k ≥ 0, a k -cover for subset Q ⊆ P is a set of at most k balls, each centered at a point in P , whose union covers (contains) Q. The cost of a set D of balls, denoted cost( D ), is the sum of the radii of those balls.
Details
- Title: Subtitle
- On clustering to minimize the sum of radii
- Creators
- Matt GibsonGaurav KanadeErik KrohnImran PirwaniKasturi Varadarajan
- Resource Type
- Conference proceeding
- Publication Details
- Proceedings of the nineteenth annual ACM-SIAM symposium on discrete algorithms, pp.819-825
- Publisher
- Society for Industrial and Applied Mathematics
- Series
- SODA '08
- Language
- English
- Date published
- 01/20/2008
- Academic Unit
- Computer Science
- Record Identifier
- 9984259466402771
Metrics
5 Record Views