On the Ball-Constrained Weighted Maximin Dispersion Problem

Abstract

The ball-constrained weighted maximin dispersion problem $({\mathrm{P}}_{\mathrm{ball}})$ is to find a point in an $n$-dimensional Euclidean ball such that the minimum of the weighted Euclidean distance from given $m$ points is maximized. We propose a new second-order cone programming relaxation for $({\mathrm{P}}_{\mathrm{ball}})$. Under the condition $m\le n$, $({\mathrm{P}}_{\mathrm{ball}})$ is polynomial-time solvable since the new relaxation is shown to be tight. In general, we prove that $({\mathrm{P}}_{\mathrm{ball}})$ is NP-hard. Then, we propose a new randomized approximation algorithm for solving $({\mathrm{P}}_{\mathrm{ball}})$, which provides a new approximation bound of $\frac{1-O(\sqrt{\ln (m)/n})}{2}$.

26 pages