Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique

作     者：Xu, Dachuan Wang, Fengmin Du, Donglei Wu, Chenchen 

作者机构：Beijing Univ Technol Coll Appl Sci 100 Pingleyuan Beijing 100124 Peoples R China Univ New Brunswick Fac Business Adm POB 4400 Fredericton NB E3B 5A3 Canada Tianjin Univ Technol Coll Sci Tianjin 300384 Peoples R China 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2016年第630卷

页      面：117-125页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：NSFC [11531014, 11501412] Collaborative Innovation Center on Beijing Society-Building and Social Governance Natural Sciences and Engineering Research Council of Canada (NSERC) grant 

主　　题：Penalty Submodular Vertex cover Primal-dual Approximation algorithm 

摘      要：The notion of penalty has been introduced into many combinatorial optimization models. In this paper, we consider the submodular vertex cover problems with linear and submodular penalties, which are two variants of the submodular vertex cover problem where not all the edges are required to be covered by a vertex cover, and the uncovered edges are penalized. The problem is to determine a vertex subset to cover some edges and penalize the uncovered edges such that the total cost including covering and penalty is minimized. To overcome the difficulty of implementing the primal-dual framework directly, we relax the two dual programs to slightly weaker versions. We then present two primal dual approximation algorithms with approximation ratios of 2 and 4, respectively. (C) 2016 Elsevier B.V. All rights reserved.