标题： 关于球约束加权最大分散问题 显示英文标题

标题： On the Ball-Constrained Weighted Maximin Dispersion Problem

摘要： 球约束加权最大最小离散问题$(\rm P_{ball})$是要在某个$n$维欧几里得球内找到一点，使得该点到给定$m$个点的加权欧几里得距离的最小值达到最大。 我们提出了一种新的二阶锥规划松弛方法来解决$(\rm P_{ball})$问题。 在条件$m\le n$下，由于新松弛方法被证明是紧的，因此$(\rm P_{ball})$可以在多项式时间内求解。 一般情况下，我们证明$({\rm P_{ball}})$是 NP 难问题。 然后，我们提出了一种求解$({\rm P_{ball}})$的新随机近似算法，得到了一个新的近似界$\frac{1-O(\sqrt{\ln(m)/n})}{2}$。 显示英文摘要

摘要： The ball-constrained weighted maximin dispersion problem $(\rm P_{ball})$ is to find a point in an $n$-dimensional Euclidean ball such that the minimum of the weighted Euclidean distance from given $m$ points is maximized. We propose a new second-order cone programming relaxation for $(\rm P_{ball})$. Under the condition $m\le n$, $(\rm P_{ball})$ is polynomial-time solvable since the new relaxation is shown to be tight. In general, we prove that $({\rm P_{ball}})$ is NP-hard. Then, we propose a new randomized approximation algorithm for solving $({\rm P_{ball}})$, which provides a new approximation bound of $\frac{1-O(\sqrt{\ln(m)/n})}{2}$.