k-Median近似计算复杂度与局部搜索近似算法分析

• 作者: 朱大铭 潘锐 肖进杰 马绍汉
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: k中间点 算法 局部搜索 近似度 设备 客户
• 年，卷（期）: 2005,（3）
• 所属期刊栏目: 算法设计与分析
• 页码范围: 392-399
• 页数: 8页
• 分类号: TP301
• 字数: 7629字
• 语种: 中文

摘要

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局部搜索求解算法的实际计算效果和该算法的改进方法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	肖进杰	山东工商学院信息与电子工程学院	9	25	3.0	4.0
2	朱大铭	山东大学计算机科学与技术学院	50	263	11.0	13.0
3	马绍汉	山东大学计算机科学与技术学院	39	302	10.0	15.0
4	潘锐	山东大学计算机科学与技术学院	3	21	2.0	3.0