节点文献
一类median问题的近似算法研究
Research on approximation algorithm for a kind of median problem
【摘要】 利用Lin和Vitter的过滤思想研究了完全图的赋权median问题,并给出了一个近似算法.此算法可在最小化破坏背包约束的条件下求得问题的一个近似比为1+ε(ε>0)的解.
【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.
【关键词】 median；
过滤规划；
集合覆盖；
近似算法；
【Key words】 median； filtered program； set cover； approximation algorithm；
【Key words】 median； filtered program； set cover； approximation algorithm；
【基金】 国家自然科学基金资助项目(10271065)
- 【文献出处】 山东大学学报(理学版) ,Journal of Shandong University(Natural Science) , 编辑部邮箱 ,2006年04期
- 【分类号】O221
- 【被引频次】1
- 【下载频次】61