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

Abstract

In this paper, we consider the k-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 G=(V,E;c) and an integer k. This problem determines a vertex set S\subseteq V such that S covers at least k edges. The objective is to minimize the total cost of the vertices in S 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 3. When the submodular penalty cost function is linear, the approximation factor of the proposed algorithm is reduced to 2, which is the best factor if the unique game conjecture holds.

Graphical abstract

Keywords

vertex cover / k-prize-collecting / primal-dual / approximation algorithm

Xiaofei Liu received PhD degree in Mathematics from Yunnan University, China in 2018. He was a postdoctoral researcher at Peking University, China. He is currently a lecturer with Yunnan University, China. His research interests include theoretical computer science and discrete optimization

Weidong Li received the PhD degree in Department of Mathematics, from Yunnan University, China in 2010. He is currently a professor at Yunnan University, China. His research interests include discrete optimization and algorithmic game theory

Jinhua Yang is currently an associate professor at Dianchi College of Yunnan University, China. His research interests include image processing, deep learning and machine learning

References

[1] Karp R M. Reducibility among combinatorial problems. In: Miller R E, Thatcher J W, Bohlinger J D, eds. Complexity of Computer Computations. Boston: Springer, 1972, 85–103

[2] Vazirani V V. Approximation Algorithms. Berlin, Heidelberg: Springer, 2001

[3] Khot S, Regev O . Vertex cover might be hard to approximate to within 2 -ε. Journal of Computer and System Sciences, 2008, 74( 3): 335–349

[4] Hochbaum D S . Approximation algorithms for the set covering and vertex cover problems. SIAM Journal on Computing, 1982, 11( 3): 555–556

[5] Bar-Yehuda R, Even S . A linear-time approximation algorithm for the weighted vertex cover problem. Journal of Algorithms, 1981, 2( 2): 198–203

[6] Bshouty N H, Burroughs L. Massaging a linear programming solution to give a 2-approximation for a generalization of the vertex cover problem. In: Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science. 1998, 298–308

[7] Hochbaum D S. The t-vertex cover problem: extending the half integrality framework with budget constraints. In: Proceedings of International Workshop on Approximation Algorithms for Combinatorial Optimization. 1998, 111–122

[8] Bar-Yehuda R . Using homogeneous weights for approximating the partial cover problem. Journal of Algorithms, 2001, 39( 2): 137–144

[9] Gandhi R, Khuller S, Srinivasan A . Approximation algorithms for partial covering problems. Journal of Algorithms, 2004, 53( 1): 55–84

[10] Mestre J . A primal-dual approximation algorithm for partial vertex cover: making educated guesses. Algorithmica, 2009, 55( 1): 227–239

[11] Hochbaum D S . Solving integer programs over monotone inequalities in three variables: a framework for half integrality and good approximations. European Journal of Operational Research, 2002, 140( 2): 291–321

[12] Bar-Yehuda R, Rawitz D . On the equivalence between the primal-dual schema and the local ratio technique. SIAM Journal on Discrete Mathematics, 2005, 19( 3): 762–797

[13] Li Y, Du D, Xiu N, Xu D . Improved approximation algorithms for the facility location problems with linear/submodular penalties. Algorithmica, 2015, 73( 2): 460–482

[14] Du D, Lu R, Xu D. A primal-dual approximation algorithm for the facility location problem with submodular penalties. Algorithmica, 2012, 63(1–2): 1–2

[15] Liu X, Li W . Approximation algorithms for the multiprocessor scheduling with submodular penalties. Optimization Letters, 2021, 15( 6): 2165–2180

[16] Liu X, Li W, Xie R. A primal-dual approximation algorithm for the k-prize-collecting minimum power cover problem. Optimization Letters, 2021,

[17] Iwata S, Nagano K. Submodular function minimization under covering constraints. In: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science. 2009, 671–680

[18] Xu D, Wang F, Du D, Wu C . Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique. Theoretical Computer Science, 2016, 630: 117–125

[19] Kamiyama N . A note on the submodular vertex cover problem with submodular penalties. Theoretical Computer Science, 2017, 659: 95–97

[20] Guo J S, Liu W, Hou B. An approximation algorithm for p-prize-collecting set cover problem. Journal of the Operations Research Society of China, 2021,

[21] Fleischer L, Iwata S . A push-relabel framework for submodular function minimization and applications to parametric optimization. Discrete Applied Mathematics, 2003, 131( 2): 311–322

[22] Kao M J, Shiau J Y, Lin C C, Lee D T . Tight approximation for partial vertex cover with hard capacities. Theoretical Computer Science, 2019, 778: 61–72

[23] Cheung W C, Goemans M X, Wong S C W. Improved algorithms for vertex cover with hard capacities on multigraphs and hypergraphs. In: Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms. 2014, 1714–1726

[24] Wong S C W. Tight algorithms for vertex cover with hard capacities on multigraphs and hypergraphs. In: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms. 2017, 2626–2637

Acknowledgements

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

RIGHTS & PERMISSIONS

2023 Higher Education Press