Show brief item record

dc.contributor.authorGibson, Matt
dc.contributor.authorKanade, Gaurav
dc.contributor.authorKrohn, Erik
dc.contributor.authorPirwani, Imran
dc.contributor.authorVaradarajan, Kasturi
dc.date.accessioned2021-12-07T21:27:27Z
dc.date.available2021-12-07T21:27:27Z
dc.date.issued2012-01-05
dc.identifier.issn1095-7111
dc.identifier.urihttps://hdl.handle.net/20.500.12588/762
dc.descriptionA 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.abstractLet 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.sponsorshipThe work of the first, second, third, and fifth authors was partially supported by NSF CAREER award CCR 0237431.en_US
dc.language.isoen_USen_US
dc.publisherSociety for Industrial and Applied Mathematicsen_US
dc.relation.ispartofseriesSIAM Journal on Computing;41(1)
dc.subjectk-clusteringen_US
dc.subjectmin-cost k-coveren_US
dc.subjectminimum sum of radii coveren_US
dc.titleOn Clustering to Minimize the Sum of Radiien_US
dc.typeArticleen_US
dc.description.departmentComputer Scienceen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show brief item record