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

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