A primal-dual approximation algorithm for the k-prize-collecting minimum vertex cover problem with submodular penalties  

作　　者：Xiaofei LIU Weidong LI Jinhua YANG 

机构地区：[1]School of Information Science and Engineering,Yunnan University,Kunming 650500,China [2]School of Mathematics and Statistics,Yunnan University,Kunming 650500,China [3]Dianchi College of Yunnan University,Kunming 650228,China

出　　处：《Frontiers of Computer Science》2023年第3期125-132,共8页中国计算机科学前沿（英文版）

基　　金：The work was supported in part by the National Natural Science Foundation of China(Grant No.12071417)。

摘　　要：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.

关 键 词：vertex cover k-prize-collecting PRIMAL-DUAL approximation algorithm 

分 类 号：O15[理学—数学]