首页 | 本学科首页   官方微博 | 高级检索  
     


A primal-dual approximation algorithm for the k-prize-collecting minimum vertex cover problem with submodular penalties
Authors:Xiaofei LIU  Weidong LI  Jinhua YANG
Affiliation:1. School of Information Science and Engineering, Yunnan University, Kunming 650500, China2. School of Mathematics and Statistics, Yunnan University, Kunming 650500, China3. Dianchi College of Yunnan University, Kunming 650228, China
Abstract:In this paper, we consider the k-prize-collecting minimum vertex cover problem with submodular penalties, which generalizes the well-known minimum vertex cover problem, minimum partial vertex cover problem and minimum vertex cover problem with submodular penalties. We are given a cost graph G=(V,E;c) and an integer k. This problem determines a vertex set S?V such that S covers at least k edges. The objective is to minimize the total cost of the vertices in S plus the penalty of the uncovered edge set, where the penalty is determined by a submodular function. We design a two-phase combinatorial algorithm based on the guessing technique and the primal-dual framework to address the problem. When the submodular penalty cost function is normalized and nondecreasing, the proposed algorithm has an approximation factor of 3. When the submodular penalty cost function is linear, the approximation factor of the proposed algorithm is reduced to 2, which is the best factor if the unique game conjecture holds.
Keywords:vertex cover  k-prize-collecting  primal-dual  approximation algorithm  
点击此处可从《Frontiers of Computer Science》浏览原始摘要信息
点击此处可从《Frontiers of Computer Science》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号