您当前所在位置: 首页 > 学者

朱大铭

  • 27浏览

  • 0点赞

  • 0收藏

  • 0分享

  • 105下载

  • 0评论

  • 引用

期刊论文

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

朱大铭潘锐马绍汉肖进杰

软件学报,2004,15(1)1~9,-0001,():

URL:

摘要/描述

The research on approximated algorithms for k-Median problem is a focus of computer scientists all along, and most existed results are based on Euclidean and Metric k-Median problem, however, results for General distance space k-Median is not 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 ortest edge for one client point. In this paper, we first prove that there are no polynomial algorithms of approximation ratio 1+e1−ωk-Median with condition dmax/dmin≤ω+ε, unlessDTIMNP⊆result implies there are no polynomial algorithms of approximation ratio 1+2elog (lognone2 for Metric k-Median unless. Then a local search algorithm for k-Median is presented. New analysis shows that local search can achieve a ratio of

【免责声明】以下全部内容由[朱大铭]上传于[2006年12月01日 02时12分37秒],版权归原创者所有。本文仅代表作者本人观点,与本网站无关。本网站对文中陈述、观点判断保持中立,不对所包含内容的准确性、可靠性或完整性提供任何明示或暗示的保证。请读者仅作参考,并请自行承担全部责任。

我要评论

全部评论 0

本学者其他成果

    同领域成果