一类median问题的近似算法研究

• 论文 • 下一篇

一类median问题的近似算法研究

王继强^1,2

山东大学数学与系统科学学院，山东济南250100

收稿日期:2005-09-14 修回日期:1900-01-01 出版日期:2006-10-24 发布日期:2006-10-24
通讯作者: 王继强

AResearch on approximation algorithm for a kind of median problem

WANG Ji-qiang

School of Math. and System Sci.， Shandong Univ.， Jinan 250100， Shandong, China

Received:2005-09-14 Revised:1900-01-01 Online:2006-10-24 Published:2006-10-24

摘要/Abstract

摘要： 利用Lin和Vitter的过滤思想研究了完全图的赋权median问题，并给出了一个近似算法.此算法可在最小化破坏背包约束的条件下求得问题的一个近似比为1+ε（ε＞0）的解.

关键词: median, 过滤规划, 近似算法 , 集合覆盖

Abstract: The idea of filtering due to Lin and Vitter is used to study the weighted median problem in complete graphs， and an approximation algorithm is presented, which outputs a solution of approximation ratio 1+ε (ε＞0) to this problem with minimum packing constraint violations.

Key words: approximation algorithm , set cover, filtered program, median

王继强, . 一类median问题的近似算法研究[J]. J4, 2006, 41(4): 1-03 .

WANG Ji-qiang . AResearch on approximation algorithm for a kind of median problem[J]. J4, 2006, 41(4): 1-03 .

参考文献

相关文章 9

[1]	蔡裕华,魏凤英*. 度量空间的概率近似算法[J]. J4, 2013, 48(09): 51-55.
[2]	杨朝霞 . 超图嵌入带权重圈的一个2-近似算法[J]. J4, 2008, 43(8): 11-13 .
[3]	杨振光,李曙光,王秀红 . 工件尺寸不同的并行机批调度问题[J]. J4, 2007, 42(4): 63-66 .
[4]	戴珍香,李曙光,亓兴勤 . 波分复用星形单跳网中3信道的传输调度问题[J]. J4, 2007, 42(2): 46-50 .
[5]	亓兴勤,曹静,张晨 . 环型二元序列的赋权对换排序问题[J]. J4, 2007, 42(12): 46-48 .
[6]	李曙光,白淑岩,何志红,亓兴勤 . 圈中t-区间的k-染色问题[J]. J4, 2006, 41(6): 40-42 .
[7]	李曙光,杨振光,何志红 . 多纤波分复用链网与环网中的利润极大化问题[J]. J4, 2006, 41(5): 7-11 .
[8]	李曙光,亓兴勤,何志红 . 环网络中的呼叫接纳控制[J]. J4, 2006, 41(4): 15-19 .
[9]	亓兴勤,何志红,赵洪銮 . 二元序列的赋权对换排序问题[J]. J4, 2006, 41(1): 82-85 .

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed