On the ball-constrained weighted maximin dispersion problem

The ball-constrained weighted maximin dispersion problem (P_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 (P_ball). Under the condition m ≤ n, (P_ball) is polynomial-time solvable since the new relaxation is shown to be tight. In general, we prove that (P_ball) is NP-hard. Then, we propose a new randomized approximation algorithm for solving (P_ball), which provides a new approximation bound (equation presented).