On Clustering to Minimize the Sum of Radii
| dc.contributor.author | Gibson, Matt | |
| dc.contributor.author | Kanade, Gaurav | |
| dc.contributor.author | Krohn, Erik | |
| dc.contributor.author | Pirwani, Imran | |
| dc.contributor.author | Varadarajan, Kasturi | |
| dc.date.accessioned | 2021-12-07T21:27:27Z | |
| dc.date.available | 2021-12-07T21:27:27Z | |
| dc.date.issued | 2012-01-05 | |
| dc.description | A preliminary version of this paper appeared in the 18th ACM-SIAMSymposium on Discrete Algorithms (SODA), San Francisco, CA, 2008, pp. 819–825. | en_US |
| dc.description.abstract | Let P be a set of n points in the plane. Consider the problem of finding k disks, each centered at a point in P, whose union covers P with the objective of minimizing the sum of the radii of the disks. We present an exact algorithm for this well-studied problem with polynomial running time, under the assumption that two candidate solutions can be compared efficiently. The algorithm generalizes in a straightforward manner to any fixed dimension and to some other related problems. | en_US |
| dc.description.department | Computer Science | en_US |
| dc.description.sponsorship | The work of the first, second, third, and fifth authors was partially supported by NSF CAREER award CCR 0237431. | en_US |
| dc.identifier.issn | 1095-7111 | |
| dc.identifier.uri | https://hdl.handle.net/20.500.12588/762 | |
| dc.language.iso | en_US | en_US |
| dc.publisher | Society for Industrial and Applied Mathematics | en_US |
| dc.relation.ispartofseries | SIAM Journal on Computing;41(1) | |
| dc.subject | k-clustering | en_US |
| dc.subject | min-cost k-cover | en_US |
| dc.subject | minimum sum of radii cover | en_US |
| dc.title | On Clustering to Minimize the Sum of Radii | en_US |
| dc.type | Article | en_US |