ON THE BALL-CONSTRAINED WEIGHTED MAXIMIN DISPERSION PROBLEM
主 题: ON THE BALL-CONSTRAINED WEIGHTED MAXIMIN DISPERSION PROBLEM
报告人: Prof. Yong Xia (Beihang University)
时 间: 2016-03-24 10:00-11:00
地 点: 北京国际数学研究中心全29教室
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}$.
