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

A factor 2-approximation algorithm for the prize-collecting vertex cover problem

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

Given a graph G with a cost function c on its vertices and a penalty function w on its edges,the cost of a subset FV is the cost of vertices in F plus the penalty of the edges not covered by F.How to find a subset F V of minimum cost,known as the prize-collecting vertex cover problem,has become a problem of widespread concern to researchers in recent years.In this paper,we give a factor 2-approximation algorithm for the prize-collecting vertex cover problem using iterative methods,and prove the correctness of our conclusion.