  Finding nonoverlapping balls with given centers in any metric space,
maximizing the sum of radii of the balls, can be expressed as a linear program.
Its dual linear program expresses the problem of finding a minimum-weight set
of cycles (allowing 2-cycles) covering all vertices in a complete geometric
graph. For points in a Euclidean space of any finite dimension~$d$, with any
convex distance function on this space, this graph can be replaced by a sparse
subgraph obeying a separator theorem. This graph structure leads to an
algorithm for finding the optimum set of balls in time $O(n^{2-1/d})$,
improving the $O(n^3)$ time of a naive cycle cover algorithm. As a subroutine,
we provide an algorithm for weighted bipartite matching in graphs with
separators, which speeds up the best previous algorithm for this problem on
planar bipartite graphs from $O(n^{3/2}\log n)$ to $O(n^{3/2})$ time. We also
show how to constrain the balls to all have radius at least a given threshold
value, and how to apply our radius-sum optimization algorithms to the problem
of embedding a finite metric space into a star metric minimizing the average
distance to the hub.
