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∈S S=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 2 f + ε-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.
Jin-Shuang Guo, Wen Liu, Bo Hou
. An Approximation Algorithm for P-prize-collecting Set Cover Problem[J]. Journal of the Operations Research Society of China, 2023
, 11(1)
: 207
-218
.
DOI: 10.1007/s40305-021-00364-7
[1] Balas, E., Padberg, M.:Set partitioning:a survey.SIAM Rev.18(4), 710-760(1976)
[2] Garfinkel, R.S., Nemhauser, G.L.:Optimal set covering:a survey.In:Geoffrion, A.M.(ed.) Perspectives on Optimization, pp.164-183.Springer, Berlin (1972)
[3] Hochbaum, D.S.:Approximating covering and packing problems:set cover, vertex cover, independent set, and related problems.In:Hochbaum, D.S.(ed.) Approx.Algorithms NP-Hard Problems, pp.94-143.PWS, Boston (1997).Chap.3
[4] Könemann, J., Parekh, O., Segev, D.:A unified approach to approximating partial covering problems.Algorithmica 59(4), 489-509(2011)
[5] Kearns, M.:The Computational Complexity of Machine Learning.MIT Press, Cambridge (1990)
[6] Gandhi, R., Khuller, S., Srinivasan, A.:Approximation algorithms for partial covering problems.J.Algorithms 53, 55-84(2004)
[7] Bar-Yehuda, R.:Using homogeneous weights for approximating the partial cover problem.J.Algorithms 39(2), 137-144(2001)
[8] Fujito, T.:On approximation of the submodular set cover problem.Oper.Res.Lett.25(4), 169-174(1999)
[9] Bar-Yehuda, R., Even, S.:A linear-time approximation algorithm for the weighted vertex cover problem.J.Algorithms 2(2), 198-203(1981)
[10] Williamson, D.P., Shmoys, D.B.:The Design of Approximation Algorithms.Cambridge University Press, Cambridge (2011)
[11] Jain, K., Vazirani, V.V.:Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation.J.ACM 48(2), 274-296(2001)
[12] Garg, N.:A 3-approximation for the minimum tree spanning k vertices.In:Proceedings of 37th Symposium on Foundations of Computer Science, pp.302-309(1996)
[13] Chudak, F.A., Roughgarden, T., Williamson, D.P.:Approximate k-MSTs and k-Steiner trees via the primal-dual method and Lagrangian relaxation.In:Proceedings of 8th Conference on Integer Programming and Combinatorial Optimization, pp.60-70(2001)
[14] Han, L., Xu, D.C., Du, D.L., Wu, C.C.:A 5-approximation algorithm for the k-prize-collecting Steiner tree problem.Optim.Lett.13, 573-585(2019)
[15] Hou, X., Liu, W., Hou, B.:An Approximation algorithm for the k-prize-collecting multicut on a tree problem.Theor.Comput.Sci.844, 26-33(2020)
[16] Levina, A., Segev, D.:Partial multicuts in trees.Theor.Comput.Sci.369, 384-395(2006)
