| k-supplier问题的贪婪近似算法 |
| |
| 引用本文： | 丁哲衡,朱芳,王勤.k-supplier问题的贪婪近似算法[J].中国计量学院学报,2012,23(4):400-402,409. |
| |
| 作者姓名： | 丁哲衡 朱芳 王勤 |
| |
| 作者单位： | 中国计量学院理学院,浙江杭州,310018 |
| |
| 基金项目： | 国家自然科学基金资助项目，浙江省教育厅科研项目 |
| |
| 摘 要： | 给定无向完全图G=(V,E)和正整数k,图G的顶点集V被划分为子集F和子集D=V-F.k-supplier问题主要研究如何寻找F中顶点数不多于k的子集S,使得S中的顶点到D中顶点的最大距离最小.研究了k-supplier问题,得到了一个近似比为3的多项式时间贪婪近似算法,并通过实例验证了该算法的有效性.
|
| 关 键 词： | k-supplier问题 贪婪算法 近似算法 |
Greedy approximation algorithm for the k-supplier problem |
| |
| DING Zhe-heng
,
ZHU Fang
,
WANG Qin.Greedy approximation algorithm for the k-supplier problem[J].Journal of China Jiliang University,2012,23(4):400-402,409. |
| |
| Authors: | DING Zhe-heng ZHU Fang WANG Qin |
| |
| Affiliation: | (College of Sciences,China Jiliang University,Hangzhou 310018,China) |
| |
| Abstract: | An undirected complete graph G=(V,E) and a positive integer k were given.The vertex set V of G was partitioned into subset F and subset D=V-F.The k-supplier problem mainly considers how to find a subset S■F,with the number of vertices not greater than k,such that the maximum distance from the vertices in S to the vertices in D is minimized.Now,we studied the k-supplier problem and we proposed a polynomial time 3-approximation greedy algorithm.We also verify the efficiency of this algorithm by giving an example. |
| |
| Keywords: | k-supplier problem greedy algorithm approximation algorithm |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
