摘要
k-Median 问题的近似算法研究一直是计算机科学工作者关注的焦点,现有研究结果大多是关于欧式空间和 Metric 空间的,一般距离空间 k-Median 的结果多年来一直未见.考虑一般距离空间 k-Median 问题,设 dmax/dmin表示 k-Median 实例中与客户点邻接的最长边长比最短边长的最大者.首先证明 dmax/dmin≤ω+ε的 k-Median 问题不存在近似度小于1+ ω ?1 (loglog n) e 的多项式时间近似算法,除非 NP ? DTIME(nO ) ,由此推出 Metric k-Median 问题不可近似到 1+ 2 (log log n) e,除非 NP ? DTIME(nO ) .然后给出 k-Median 问题的一个局部搜索算法,分析表明,若有 dmax/dmin≤ω,则算法的近似度为 1+ ω2 .该结果亦适用于 Metric k-Median,ω≤5 时,局部搜索算法求解 Metric k-Median 的 ?1近似度为 3,好于现有结果 3+ 2 .通过计算机实验,进一步研究了 k-Median 局部搜索求解算法的实际计算效果和该 p算法的改进方法.
Research on the approximated algorithms for k-Median problem has been a focus of computer scientists, and most of the existing results are based on the Euclidean and Metric k-Median problem. However, results for general distance space k-Median has not been found for many years. In general distance space, let dmax/dmin denote the maximum value of the length of the longest edge divided by the length of the shortest edge for one client point. In this paper, it is first proved that there are no polynomial algorithms of approximation ratio 1+ ω ?1 e for k-Median with the condition dmax/dmin≤ω+?, unless NP ? DTIME(nO (loglog n)) . This result implies there are no polynomial algorithms of approximation ratio 1+ 2 (loglog n) e for Metric k-Median unless NP ? DTIME(nO ) . Then a local search algorithm for k-Median is presented. New analysis shows that the local search can achieve a ratio of 1+ ω ?1 2 . This result can also be extended to the Metric k-Median, and if ω≤5, the local search algorithm can achieve a ratio less than 3 for the Metric k-Median, which is better than the existing best ratio 3+ 2 . Finally, p computer verification is used to study the real computational effect and the improved method of the local search algorithm.
出处
《软件学报》
EI
CSCD
北大核心
2005年第3期392-399,共8页
Journal of Software
基金
国家自然科学基金~~
关键词
κ中间点
算法
局部搜索
近似度
设备
客户
k-median
algorithm
local search
approximation ratio
facility
client