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 - 2016-03-24 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}$.
