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

作     者：Xiaofei LIU Weidong LI Jinhua YANG Xiaofei LIU;Weidong LI;Jinhua YANG

作者机构：School of Information Science and EngineeringYunnan UniversityKunming 650500China School of Mathematics and StatisticsYunnan UniversityKunming 650500China Dianchi College of Yunnan UniversityKunming 650228China 

出 版 物：《Frontiers of Computer Science》 (中国计算机科学前沿（英文版）)

年 卷 期：2023年第17卷第3期

页      面：125-132页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

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

主　　题：vertex cover k-prize-collecting primal-dual approximation algorithm 

摘      要：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 *** are given a cost graph and an *** problem determines a vertex set such that covers at least *** 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 *** design a two-phase combinatorial algorithm based on the guessing technique and the primal-dual framework to address the *** the submodular penalty cost function is normalized and nondecreasing,the proposed algorithm has an approximation factor *** 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.