On the Ball-Constrained Weighted Maximin Dispersion Problem
Time: 2016-10-18
Published By: Qi Liu
Speaker(s): Prof. Yong Xia(Beihang University)
Time: 10:00-11:00 March 24, 2016
Venue: Room 29, Quan Zhai, BICMR
The ball-constrained weighted maximin dispersion problem P_{ball} is to find in an n-dimensional Euclidean ball the furthest point from given m points. We propose a new second-order cone programming relaxation for P_{ball} and show that it is tight under the condition m is less than or equal to n. We prove that P_{ball} is NP-hard in general. Then, we propose a new approximation algorithm for solving P_{ball}, which provides a new approximation bound of $\frac{1-O(\sqrt{\ln(m)/n})}{2}$.