| k-Median近似计算复杂度与局部搜索近似算法分析 |
| |
| 引用本文： | 潘锐,朱大铭,马绍汉,肖进杰.k-Median近似计算复杂度与局部搜索近似算法分析[J].软件学报,2005,16(3):392-399. |
| |
| 作者姓名： | 潘锐 朱大铭 马绍汉 肖进杰 |
| |
| 作者单位： | 山东大学,计算机科学与技术学院,山东,济南,250061;山东大学,计算机科学与技术学院,山东,济南,250061;山东大学,计算机科学与技术学院,山东,济南,250061;山东工商学院,信息与电子工程学院,山东,烟台,264005 |
| |
| 基金项目： | Supported by the National Natural Science Foundation of China under Grant Nos.60073042, 60273032 (国家自然科学基金) |
| |
| 摘 要： | 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局部搜索求解算法的实际计算效果和该算法的改进方法.
|
| 关 键 词： | k中间点 算法 局部搜索 近似度 设备 客户 |
| 文章编号： | 1000-9825/2005/16(03)0392 |
| 收稿时间： | 2003/9/12 0:00:00 |
| 修稿时间： | 7/6/2004 12:00:00 AM |
Approximated Computational Hardness and Local Search Approximated Algorithm Analysis for k-Median Problem |
| |
| PAN Rui,ZHU Da-Ming,MA Shao-Han and XIAO Jin-Jie.Approximated Computational Hardness and Local Search Approximated Algorithm Analysis for k-Median Problem[J].Journal of Software,2005,16(3):392-399. |
| |
| Authors: | PAN Rui ZHU Da-Ming MA Shao-Han and XIAO Jin-Jie |
| |
| Abstract: | |
| |
| Keywords: | k-median algorithm local search approximation ratio facility client |
| 本文献已被 CNKI 维普 等数据库收录！ |
| 点击此处可从《软件学报》浏览原始摘要信息 |
|
点击此处可从《软件学报》下载全文 |
|
