Gibson, MattKanade, GauravKrohn, ErikPirwani, ImranVaradarajan, Kasturi2021-12-072021-12-072012-01-051095-7111https://hdl.handle.net/20.500.12588/762A preliminary version of this paper appeared in the 18th ACM-SIAMSymposium on Discrete Algorithms (SODA), San Francisco, CA, 2008, pp. 819–825.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-USk-clusteringmin-cost k-coverminimum sum of radii coverArticle