| k-Median近似计算复杂度与局部搜索近似算法分析 |
| |
| 引用本文： | 潘锐,朱大铭,马绍汉,肖进杰. k-Median近似计算复杂度与局部搜索近似算法分析[J]. 软件学报, 2005, 16(3) |
| |
| 作者姓名： | 潘锐 朱大铭 马绍汉 肖进杰 |
| |
| 摘 要： | 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(NOlog logn)).然后给出k-Median问题的一个局部搜索算法,分析表明,若有dmax/dmin≤ω,则算法的近似度为1+ω-1/2.该结果亦适用于Metric k-Median,ω≤5时,局部搜索算法求解Metric k-Median的近似度为3,好于现有结果3+2/P.通过计算机实验,进一步研究了k-Median局部搜索求解算法的实际计算效果和该算法的改进方法.
|
| 关 键 词： | k中间点 算法 局部搜索 近似度 设备 客户 |
Approximated Computational Hardness and Local Search Approximated Algorithm Analysis for k-Median Problem |
| |
| PAN Rui,ZHU Da-ming,Ma Shao-han,XIAO Jin-Jie. Approximated Computational Hardness and Local Search Approximated Algorithm Analysis for k-Median Problem[J]. Journal of Software, 2005, 16(3) |
| |
| Authors: | PAN Rui ZHU Da-ming Ma Shao-han XIAO Jin-Jie |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 万方数据 等数据库收录！ |
|
