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

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

作　　者：杜俊峰[1] 涂建华[1] 

机构地区：[1]北京化工大学理学院,北京100029

出　　处：《北京化工大学学报（自然科学版）》2014年第2期120-123,共4页Journal of Beijing University of Chemical Technology(Natural Science Edition)

基　　金：国家自然科学基金青年基金(11201021)

摘　　要：给定图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.

关 键 词：组合优化 奖励收集顶点覆盖问题 迭代松弛方法 近似算法 

分 类 号：O157.5[理学—数学]