On the Ball-Constrained Weighted Maximin Dispersion Problem
On the Ball-Constrained Weighted Maximin Dispersion Problem
复制标题
关于球约束加权最大最小离散度问题
DOI：
10.1137/15m1047167
复制
发表时间：
2016-04
影响因子：
3.1
通讯作者：
Xia Yong
中科院分区：
文献类型：
--
作者：
Wang Shu;Xia Yong
球约束加权最大最小色散问题 $(\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}$.
登录
查看更多内容
DOI：
10.1016/0020-0190(85)90102-4
发表时间：
1985-07
期刊：
Inf. Process. Lett.
影响因子：
--
作者：
G. Guralnik;C. Zemach;T. Warnock
通讯作者：
G. Guralnik;C. Zemach;T. Warnock
DOI：
10.1137/s1052623401392354
发表时间：
2002-06
期刊：
SIAM J. Optim.
影响因子：
--
作者：
A. Ben-Tal;A. Nemirovski;Kees Roos
通讯作者：
A. Ben-Tal;A. Nemirovski;Kees Roos
影响因子：
4.3
作者：
Y. Tenne;K. Izui;S. Nishiwaki
通讯作者：
Y. Tenne;K. Izui;S. Nishiwaki
影响因子：
10.2
作者：
HAGER, WW
通讯作者：
HAGER, WW
影响因子：
1.7
作者：
Simai He;Jiang Bo;Zhening Li;Shuzhong Zhang
通讯作者：
Shuzhong Zhang