On the Ball-Constrained Weighted Maximin Dispersion Problem
发布时间:2016年10月18日
浏览次数:9590
发布者: Qi Liu
主讲人: Prof. Yong Xia(Beihang University)
活动时间: 从 2016-03-24 10:00 到 11:00
场地: 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}$.