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

doi:10.1007/s11704-022-1665-9

Front. Comput. Sci.

2023, Vol. 17

Issue (3) : 173404 https://doi.org/10.1007/s11704-022-1665-9

RESEARCH ARTICLE

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

Xiaofei LIU¹, Weidong LI²(

), Jinhua YANG³

¹. School of Information Science and Engineering, Yunnan University, Kunming 650500, China
². School of Mathematics and Statistics, Yunnan University, Kunming 650500, China
³. Dianchi College of Yunnan University, Kunming 650228, China

Download: PDF(2172 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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 ⊆ 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.

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

Corresponding Author(s): Weidong LI

About author:

Tongcan Cui and Yizhe Hou contributed equally to this work.

Just Accepted Date: 22 April 2022 Issue Date: 20 October 2022

Cite this article:

Xiaofei LIU,Weidong LI,Jinhua YANG. A primal-dual approximation algorithm for the k-prize-collecting minimum vertex cover problem with submodular penalties[J]. Front. Comput. Sci., 2023, 17(3): 173404.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-022-1665-9
https://academic.hep.com.cn/fcs/EN/Y2023/V17/I3/173404

Fig.1 For instance

I = (G; c, π; k)

, we illustrate Phase 1 in a, b and c; and illustrate Phase 2 in d and e

Fig.2 The relationship of

E ′

E 1 ′

and

E 2 ′

1	R M Karp . 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	V V Vazirani . Approximation Algorithms. Berlin, Heidelberg: Springer, 2001
3	S, Khot O Regev . Vertex cover might be hard to approximate to within 2 -ε. Journal of Computer and System Sciences, 2008, 74( 3): 335–349
4	D S Hochbaum . Approximation algorithms for the set covering and vertex cover problems. SIAM Journal on Computing, 1982, 11( 3): 555–556
5	R, Bar-Yehuda S Even . A linear-time approximation algorithm for the weighted vertex cover problem. Journal of Algorithms, 1981, 2( 2): 198–203
6	N H, Bshouty L Burroughs . 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	D S Hochbaum . 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	R Bar-Yehuda . Using homogeneous weights for approximating the partial cover problem. Journal of Algorithms, 2001, 39( 2): 137–144
9	R, Gandhi S, Khuller A Srinivasan . Approximation algorithms for partial covering problems. Journal of Algorithms, 2004, 53( 1): 55–84
10	J Mestre . A primal-dual approximation algorithm for partial vertex cover: making educated guesses. Algorithmica, 2009, 55( 1): 227–239
11	D S Hochbaum . 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	R, Bar-Yehuda D Rawitz . On the equivalence between the primal-dual schema and the local ratio technique. SIAM Journal on Discrete Mathematics, 2005, 19( 3): 762–797
13	Y, Li D, Du N, Xiu D Xu . Improved approximation algorithms for the facility location problems with linear/submodular penalties. Algorithmica, 2015, 73( 2): 460–482
14	D, Du R, Lu D Xu . A primal-dual approximation algorithm for the facility location problem with submodular penalties. Algorithmica, 2012, 63(1–2): 1–2
15	X, Liu W Li . Approximation algorithms for the multiprocessor scheduling with submodular penalties. Optimization Letters, 2021, 15( 6): 2165–2180
16	X, Liu W, Li R Xie . A primal-dual approximation algorithm for the k-prize-collecting minimum power cover problem. Optimization Letters, 2021, DOI: https://doi.org/10.1007/s11590-021-01831-z
17	S, Iwata K Nagano . Submodular function minimization under covering constraints. In: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science. 2009, 671–680
18	D, Xu F, Wang D, Du C Wu . Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique. Theoretical Computer Science, 2016, 630: 117–125
19	N Kamiyama . A note on the submodular vertex cover problem with submodular penalties. Theoretical Computer Science, 2017, 659: 95–97
20	J S, Guo W, Liu B Hou . An approximation algorithm for p-prize-collecting set cover problem. Journal of the Operations Research Society of China, 2021, DOI: https://doi.org/10.1007/s40305-021-00364-7
21	L, Fleischer S Iwata . A push-relabel framework for submodular function minimization and applications to parametric optimization. Discrete Applied Mathematics, 2003, 131( 2): 311–322
22	M J, Kao J Y, Shiau C C, Lin D T Lee . Tight approximation for partial vertex cover with hard capacities. Theoretical Computer Science, 2019, 778: 61–72
23	W C, Cheung M X, Goemans S C W Wong . 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	S C W Wong . 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

[1]

FCS-21665-OF-XL_suppl_1

Download

[1]	Peng ZHANG. The LP-rounding plus greed approach for partial optimization revisited[J]. Front. Comput. Sci., 2022, 16(1): 161402-.
[2]	Yun PENG, Xin LIN, Byron CHOI, Bingsheng HE. *VColor: a practical approach for coloring large graphs**[J]. Front. Comput. Sci., 2021, 15(4): 154610-.
[3]	Yudong QIN, Deke GUO, Zhiyao HU, Bangbang REN. Uncertain multicast under dynamic behaviors[J]. Front. Comput. Sci., 2020, 14(1): 130-145.
[4]	Xingshen SONG, Yuexiang YANG, Yu JIANG, Kun JIANG. Optimizing partitioning strategies for faster inverted index compression[J]. Front. Comput. Sci., 2019, 13(2): 343-356.
[5]	Peng ZHANG. Unbalanced graph cuts with minimum capacity[J]. Front. Comput. Sci., 2014, 8(4): 676-683.
[6]	Deying LI, Qinghua ZHU, Jiannong CAO, . Approximation algorithm for constructing data aggregation trees for wireless sensor networks[J]. Front. Comput. Sci., 2009, 3(4): 524-534.

Viewed

Full text

Abstract

Cited

Shared

Discussed