An Approximation Algorithm for P-prize-collecting Set Cover Problem  

作　　者：Jin-Shuang Guo Wen Liu Bo Hou 

机构地区：[1]School of Mathematical Sciences,Hebei Key Laboratory of Computational Mathematics and Applications,Hebei Normal University,Shijiazhuang,050024,Hebei,China

出　　处：《Journal of the Operations Research Society of China》2023年第1期207-217,共11页中国运筹学会会刊（英文）

基　　金：This work was supported by the National Natural Science Foundation of China(No.11971146);the Natural Science Foundation of Hebei Province of China(Nos.A2019205089 and A2019205092);Hebei Province Foundation for Returnees(No.CL201714);Overseas Expertise Introduction Program of Hebei Auspices(No.25305008).

摘　　要：In this paper,we consider the P-prize-collecting set cover(P-PCSC)problem,which is a generalization of the set cover problem.In this problem,we are given a set system(U,S),where U is a ground set and S⊆2U is a collection of subsets satisfying∪S∈SS=U.Every subset in S has a nonnegative cost,and every element in U has a nonnegative penalty cost and a nonnegative profit.Our goal is to find a subcollection C⊆S such that the total cost,consisting of the cost of subsets in C and the penalty cost of the elements not covered by C,is minimized and at the same time the combined profit of the elements covered by C is at least P,a specified profit bound.Our main work is to obtain a 2f+ε-approximation algorithm for the P-PCSC problem by using the primal-dual and Lagrangian relaxation methods,where f is the maximum frequency of an element in the given set system(U,S)andεis a fixed positive number.

关 键 词：P-prize-collecting set cover problem Approximation algorithm PRIMAL-DUAL Lagrangian relaxation 

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