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

doi:10.1007/s40305-021-00364-7

Journal of the Operations Research Society of China ›› 2023, Vol. 11 ›› Issue (1): 207-218.doi: 10.1007/s40305-021-00364-7

Previous Articles Next Articles

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

Jin-Shuang Guo, Wen Liu, Bo Hou

School of Mathematical Sciences, Hebei Key Laboratory of Computational Mathematics and Applications, Hebei Normal University, Shijiazhuang 050024, Hebei, China

Received:2021-01-14 Revised:2021-04-27 Online:2023-03-30 Published:2023-02-28
Contact: Bo Hou, Jin-Shuang Guo, Wen Liu E-mail:houbo1969@163.com;779439710@qq.com;liuwen1975@126.com
Supported by:
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) and Overseas Expertise Introduction Program of Hebei Auspices (No.25305008).

Abstract

Abstract: 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 ⊆ 2^U 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.

Key words: P-prize-collecting set cover problem, Approximation algorithm, Primal-dual, Lagrangian relaxation

CLC Number:

68W25
68W40

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.

TrendMD

References

[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)

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	Wei Yu, Rui-Yong Dai, Zhao-Hui Liu. Approximation Algorithms for Multi-vehicle Stacker Crane Problems [J]. Journal of the Operations Research Society of China, 2023, 11(1): 109-132.
[2]	Lei Zhao, Dao-Li Zhu. On Iteration Complexity of a First-Order Primal-Dual Method for Nonlinear Convex Cone Programming [J]. Journal of the Operations Research Society of China, 2022, 10(1): 53-87.
[3]	Xiao-Dan Jia, Bo Hou, Wen Liu. An Approximation Algorithm for the Generalized Prize-Collecting Steiner Forest Problem with Submodular Penalties [J]. Journal of the Operations Research Society of China, 2022, 10(1): 183-192.
[4]	Zhong-Zheng Tang, Zhuo Diao. Approximation Algorithms on k-Cycle Transversal and k-Clique Transversal [J]. Journal of the Operations Research Society of China, 2021, 9(4): 883-892.
[5]	Ru-Bing Chen, Ling-Fa Lu, Jin-Jiang Yuan, Li-Qi Zhang. Improved Approximation Algorithm for Scheduling on a Serial Batch Machine with Split-Allowed Delivery [J]. Journal of the Operations Research Society of China, 2020, 8(1): 133-143.
[6]	Yao Xu, Yong Chen, Peng Zhang, Randy Goebel. Approximation Algorithms for Vertex Happiness [J]. Journal of the Operations Research Society of China, 2019, 7(3): 429-448.
[7]	Xiang Gao, Yang-Yang Xu, Shu-Zhong Zhang. Randomized Primal–Dual Proximal Block Coordinate Updates [J]. Journal of the Operations Research Society of China, 2019, 7(2): 205-250.
[8]	Tao-Ran Fu, Jin-Yan Fan. Successive Partial-Symmetric Rank-One Algorithms for Almost Unitarily Decomposable Conjugate Partial-Symmetric Tensors [J]. Journal of the Operations Research Society of China, 2019, 7(1): 147-167.
[9]	Behrouz Kheirfam. A Modified and Simplified Full Nesterov–Todd Step O(N) Infeasible Interior-Point Method for Second-Order Cone Optimization [J]. Journal of the Operations Research Society of China, 2018, 6(2): 301-315.
[10]	Lu Han · Da-Chuan Xu · Dong-Lei Du·Chen-Chen Wu. A Primal-Dual Algorithm for the Generalized Prize-Collecting Steiner Forest Problem [J]. Journal of the Operations Research Society of China, 2017, 5(2): 219-.
[11]	Hong-Zhi He. Analysis of a Joint Pricing and Seat Allocation Model in a Hub-to-Hub Airline Network [J]. Journal of the Operations Research Society of China, 2016, 4(3): 309-.
[12]	Jian Li· Yu Liu. Approximation Algorithms for Stochastic Combinatorial Optimization Problems [J]. Journal of the Operations Research Society of China, 2016, 4(1): 1-.
[13]	Shi-Sheng Li · Ren-Xia Chen. Scheduling a Bounded Parallel-Batching Machine with Incompatible Job Families and Rejection [J]. Journal of the Operations Research Society of China, 2014, 2(4): 499-.
[14]	Chen-Chen Wu · Da-Chuan Xu · Jia Shu. An Approximation Algorithm for the Stochastic Fault-Tolerant Facility Location Problem [J]. Journal of the Operations Research Society of China, 2013, 1(4): 511-522.
[15]	Jia-Ting Shao · Da-Chuan Xu. An Approximation Algorithm for the Risk-Adjusted Two-Stage Stochastic Facility Location Problem with Penalties [J]. Journal of the Operations Research Society of China, 2013, 1(3): 339-346.