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

详细信息    查看全文

• 作者：Dachuan Xu^a ; ¹ ; ^{xudc@bjut.edu.cn" class="auth_mail" title="E-mail the corresponding author} ; Fengmin Wang^a ; Donglei Du^b ; ² ; Chenchen Wu^c ; ³
• 关键词：Penalty ; Submodular ; Vertex cover ; Primal-dual ; Approximation algorithm
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：30 May 2016
• 年：2016
• 卷：630
• 期：Complete
• 页码：117-125
• 全文大小：281 K

文摘

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.