Assigning Weights to Minimize the Covering Radius in the Plane

Given a set $P$ of $n$ points in the plane and a multiset $W$ of $k$ weights with $k\le n$, we assign each weight in $W$ to a distinct point in $P$ to minimize the maximum weighted distance from the weighted center of $P$ to any point in $P$. In this paper, we give two algorithms which take $O(k^2n^2\log^3 n)$timeand$O(k^5n\log^3k+kn\log^3 n)$time,respectively\mathrm{.}Foraconstant$k$,thesecondalgorithmtakesonly$O(n\log^3n)$ time, which is near linear.