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 -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 and an integer . This problem determines a vertex set such that covers at least edges. The objective is to minimize the total cost of the vertices in 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 . When the submodular penalty cost function is linear, the approximation factor of the proposed algorithm is reduced to , 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》下载全文 |
|