PDF(1121 KB)
PDF(1121 KB)
PDF(1121 KB)
奖励收集顶点覆盖问题的一个2-近似算法
A factor 2-approximation algorithm for the prize-collecting vertex cover problem
给定图G、点赋权函数c和边惩罚费用w，对于图中任一顶点子集FV，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 FV 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.
[1]Bondy J A, Murty U S R. Graph theory with applications[M]. New York: Macmillan Press Ltd, 1976.
[2]Balas E. The prize collecting traveling salesman problem[J]. Networks, 1989, 19: 621-636.
[3]Bienstock D, Goemans M X, Simchi-Levi D, et al. A note on the prize collecting traveling salesman problem[J]. Mathematical Programming, 1993, 59: 413-420. [4]Hochbaum D S. Solving integer programs over monotone inequalities in three variables A framework for half integrality and good approximations[J]. European Journal of Operational Research, 2002, 140: 291-321.
[5]Bar-Yehuda R, Flysher G, Mestre J, et al. Approximation of partial capacitated vertex cover[J]. SIAM J. on Discrete Mathematics, 2010, 24(4): 1441-1469.
[6]Roy S. Primal dual approximation algorithms or, partially covering topics in partial covering[R/OL]. [2013-04-09]. http:∥research.microsoft.com/enus/events/indiaschooljan2011/sambuddha.pdf.
[7]Jain K, A factor 2 approximation algorithm for the generalized Steiner Network problem[J]. Combinatorica, 2001, 21(1): 39-60.
[8]Lau L C, Ravi R, Singh M. Iterative methods in combinatorial optimization[M]. Cambridge: Cambridge University Press, 2011.
/
| 〈 |
|
〉 |
