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

Research on approximation algorithm for a kind of median problem

作　　者：王继强[1] 

机构地区：[1]山东大学数学与系统科学学院

出　　处：《山东大学学报（理学版）》2006年第4期1-3,共3页Journal of Shandong University(Natural Science)

基　　金：国家自然科学基金资助项目(10271065)

摘　　要：利用Lin和Vitter的过滤思想研究了完全图的赋权median问题,并给出了一个近似算法.此算法可在最小化破坏背包约束的条件下求得问题的一个近似比为1+ε(ε>0)的解.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 ＋ ε （ arbitary ε 〉 0） to this problem with minimum packing constraint violations.

关 键 词：MEDIAN 过滤规划 集合覆盖 近似算法 

分 类 号：O224[理学—运筹学与控制论]