| 一类median问题的近似算法研究 |
| |
| 引用本文： | 王继强.一类median问题的近似算法研究[J].山东大学学报(理学版),2006,41(4):1-03. |
| |
| 作者姓名： | 王继强 |
| |
| 作者单位： | 山东大学,数学与系统科学学院,山东,济南,250100;山东财政学院,统计与数理学院,山东,济南,250014 |
| |
| 摘 要： | 利用Lin和Vitter的过滤思想研究了完全图的赋权median问题，并给出了一个近似算法.此算法可在最小化破坏背包约束的条件下求得问题的一个近似比为1+ε（ε＞0）的解.
|
| 关 键 词： | median 过滤规划 集合覆盖 近似算法 |
| 文章编号： | 1671-9352（2006）04-0001-03 |
| 收稿时间： | 2005-09-14 |
| 修稿时间： | 2005年9月14日 |
AResearch on approximation algorithm for a kind of median problem |
| |
| WANG Ji-qiang.AResearch on approximation algorithm for a kind of median problem[J].Journal of Shandong University,2006,41(4):1-03. |
| |
| Authors: | WANG Ji-qiang |
| |
| Institution: | 1. School of Math. and System Sci., Shandong Univ., Jinan 250100, Shandong, China; 2. Department of Statistics and Mathernaties, Shandong Finanee Institute, Jinan 250014, Shandong, China |
| |
| 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. |
| |
| Keywords: | median |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《山东大学学报(理学版)》浏览原始摘要信息 |
| 点击此处可从《山东大学学报(理学版)》下载免费的PDF全文 |
