主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第10期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
潘锐,朱大铭,马绍汉,肖进杰.k-Median近似计算复杂度与局部搜索近似算法分析.软件学报,2005,16(3):392-399
k-Median近似计算复杂度与局部搜索近似算法分析
Approximated Computational Hardness and Local Search Approximated Algorithm Analysis for k-Median Problem
投稿时间:2003-09-12  修订日期:2004-07-06
DOI:
中文关键词:  k中间点  算法  局部搜索  近似度  设备  客户
英文关键词:k-median  algorithm  local search  approximation ratio  facility  client
基金项目:Supported by the National Natural Science Foundation of China under Grant Nos.60073042, 60273032 (国家自然科学基金)
作者单位
潘锐 山东大学,计算机科学与技术学院,山东,济南,250061 
朱大铭 山东大学,计算机科学与技术学院,山东,济南,250061 
马绍汉 山东大学,计算机科学与技术学院,山东,济南,250061 
肖进杰 山东工商学院,信息与电子工程学院,山东,烟台,264005 
摘要点击次数: 3994
全文下载次数: 4492
中文摘要:
      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阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利