New Approximation Algorithms for Weighted Maximin Dispersion Problem with Box or Ball Constraints

In this paper, we propose new approximation algorithms for a NP-hard problem, i.e., weighted maximin dispersion problem. By using a uniformly distributed random sample method, we first propose a new random approximation algorithm for box constrained or ball constrained weighted maximin dispersion problems and analyze its approximation bound respectively. Moreover, we propose two improved approximation algorithms by combining our technique with an existing binary sample technique for both cases. To the best of our knowledge, they are the best approximation bounds for both box constrained and ball constrained weighted maximin dispersion problems respectively.