奖励收集顶点覆盖问题的一个2-近似算法

作者：杜俊峰; 涂建华

来源：北京化工大学学报(自然科学版), 2014, (02): 120-123.

DOI：10.13543/j.cnki.bhxbzr.2014.02.001

• 组合优化
• 奖励收集顶点覆盖问题
• 迭代松弛方法
• 近似算法 combinatorial optimization
• prize-collecting vertex cover problem
• iterative method
• approximation algorithm

给定图G、点赋权函数c和边惩罚费用w,对于图中任一顶点子集FV,F的权重可定义为其包含的顶点权重之和加上图G中未被其覆盖的边的费用之和。如何寻找一个权重最小的顶点子集F是近年来研究者广泛关注的问题之一。这一问题被称作奖励收集顶点覆盖问题。本文采用迭代松弛方法给出了这一问题的一个近似算法,并证明了该算法的近似度为2。

• 出版日期2014
• 单位北京化工大学