Maximum Dispersion and Geometric Maximum Weight Cliques
Maximum Dispersion and Geometric Maximum Weight Cliques
复制标题
最大分散和几何最大权重团
DOI：
10.1007/s00453-003-1074-x
复制
发表时间：
2000
期刊：
影响因子：
1.1
通讯作者：
H. Meijer
中科院分区：
文献类型：
--
作者：
S. Fekete;H. Meijer
摘要
我们考虑一个
设施选址问题，目标是
“分散”一些设施，即，选择
来自N个候选者的离散集合的给定数目k个位置，
使得所选位置之间的平均距离
最大化。
特别是，我们提出了算法
结果的情况下，顶点是
由d维空间中的点表示，
边权重对应于直线
的距离.这类问题已经被考虑过了
之前，最好的结果是
近似算法，性能比为2。
对于k固定的情况，我们建立一个
线性时间算法，找到一个最佳的
溶液对于k是的一部分的情况，
输入，我们提出了一个多项式时间
近似方案
Abstract
We consider a
facility location problem, where the objective is to
“disperse” a number of facilities, i.e., select
a given number k of locations from a discrete set of n candidates,
such that the average distance between selected locations
is maximized.
In particular, we present algorithmic
results for the case where vertices are
represented by points in d-dimensional space,
and edge weights correspond to rectilinear
distances. Problems of this type have been considered
before, with the best result being an
approximation algorithm with performance ratio 2.
For the case where k is fixed, we establish a
linear-time algorithm that finds an optimal
solution. For the case where k is part of
the input, we present a polynomial-time
approximation scheme.