k-Median近似计算复杂度与局部搜索近似算法分析
Approximated Computational Hardness and Local Search Approximated Algorithm Analysis for k-Median Problem

DOI：

 作者 单位 潘锐 山东大学,计算机科学与技术学院,山东,济南,250061 朱大铭 山东大学,计算机科学与技术学院,山东,济南,250061 马绍汉 山东大学,计算机科学与技术学院,山东,济南,250061 肖进杰 山东工商学院,信息与电子工程学院,山东,烟台,264005

k-Median问题的近似算法研究一直是计算机科学工作者关注的焦点,现有研究结果大多是关于欧式空间和Metric空间的,一般距离空间k-Median的结果多年来一直未见.考虑一般距离空间k-Median问题,设dmax/dmin表示k-Median实例中与客户点邻接的最长边长比最短边长的最大者.首先证明dmax/dmin≤ω+ε的k-Median问题不存在近似度小于1+ω-1/e的多项式时间近似算法,除非,由此推出Metric k-Median问题不可近似到1+2/e,除非NP(∈)DTME(NO(log logn)).然后给出k-Median问题的一个局部搜索算法,分析表明,若有dmax/dmin≤ω,则算法的近似度为1+ω-1/2.该结果亦适用于Metric k-Median,ω≤5时,局部搜索算法求解Metric k-Median的近似度为3,好于现有结果3+2/P.通过计算机实验,进一步研究了k-Median局部搜索求解算法的实际计算效果和该算法的改进方法.

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/e for Metric k-Median unless NP=DTIME(nO(loglogn)). 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/p. Finally, p computer verification is used to study the real computational effect and the improved method of the local search algorithm.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器