×

zbMATH — the first resource for mathematics

Approximation algorithm for the partial set multi-cover problem. (English) Zbl 1433.90144
Summary: Partial set cover problem and set multi-cover problem are two generalizations of the set cover problem. In this paper, we consider the partial set multi-cover problem which is a combination of them: given an element set \(E\), a collection of sets \(\mathcal S \subseteq 2^E\), a total covering ratio \(q\), each set \(S \in \mathcal S\) is associated with a cost \(c_S\), each element \(e \in E\) is associated with a covering requirement \(r_e\), the goal is to find a minimum cost sub-collection \(\mathcal{S}'\subseteq\mathcal{S}\) to fully cover at least \(q|E|\) elements, where element \(e\) is fully covered if it belongs to at least \(r_e\) sets of \(\mathcal{S}'\). Denote by \(r_{\max}=\max\{r_e : e \in E\}\) the maximum covering requirement. We present an \((O(r_{\max}\log^2n(1 + \ln(\frac{1}{\varepsilon}) + \frac{1-q}{\varepsilon q})), 1-\varepsilon)\)-bicriteria approximation algorithm, that is, the output of our algorithm has cost \(O(r_{\max}\log^2 n(1 + \ln(\frac{1}{\varepsilon}) + \frac{1-q}{\varepsilon q}))\) times of the optimal value while the number of fully covered elements is at least \((1-\varepsilon) q|E|\).
MSC:
90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer, Berlin (2003) · Zbl 0937.68002
[2] Bar-Yuhuda, R., Using homogeneous weights for approximating the partial cover problem, J. Algorithms, 39, 137-144 (2001) · Zbl 0974.68236
[3] Bar-Yuhuda, R.; Even, S., A local-ratio theorem for approximating the weighted vertex cover problem, N.-Holl. Math. Stud., 109, 27-45 (1985)
[4] Charikar, M., Khuller, S., Mount, D.M., Narasimhan, G.: Algorithms for facility location problems with outliers. In: Proceedings 12th ACM-SIAM Symposium Discrete Algorithms, pp. 642-651 (2001) · Zbl 1012.90026
[5] Chekuri, Chandra; Ene, Alina; Vakilian, Ali, Prize-Collecting Survivable Network Design in Node-Weighted Graphs, 98-109 (2012), Berlin, Heidelberg · Zbl 1372.68206
[6] Chekuri, C.; Even, G.; Gupta, A.; Segev, D., Set connectivity problems in undirected graphs and the directed steiner network problem, ACM Trans. Algorithms, 7, 18:1-18:7 (2011) · Zbl 1295.68211
[7] Chvatal, V., A greedy heuristic for the set-covering problem, Math. Oper. Res., 4, 233-235 (1979) · Zbl 0443.90066
[8] Dinur, I.; Steurer, D., Analytical approach to parallel repetition, STOC, 2014, 624-633 (2014) · Zbl 1315.91001
[9] Dobson, G., Worst-case analysis of greedy heuristics for integer programming with nonnegatice data, Math. Oper. Res., 7, 515-531 (1982) · Zbl 0498.90061
[10] Feige, U.: A threshold of ln n for approximating set cover. In: Proceedings 28th ACM Symposium on the Theory of Computing, pp. 312-318 (1996) · Zbl 0922.68067
[11] Gandhi, R.; Khuller, S.; Srinivasan, A., Approximation algorithms for partial covering problems, J. Algorithms, 53, 55-84 (2004) · Zbl 1068.68177
[12] Hajiaghayi, M.; Khandekar, R.; Kortsarz, G.; Nutov, Z., Prize-collecting Steiner network problems, IPCO, 2010, 71-84 (2010) · Zbl 1285.90049
[13] Hochbaum, DS, Approximation algorithms for the set covering and vertex cover problems, SIAM J. Comput., 11, 555-556 (1982) · Zbl 0486.68067
[14] Ignizio, J.P., Cavalier, T.M.: Linear Programming. Prentice-Hall, Inc., Upper Saddle River (1994)
[15] Johnson, DS, Approximation algorithms for combinatorial problems, J. Comput. Syst Sci., 9, 256-278 (1974) · Zbl 0296.65036
[16] Karp, RM; Miller, RE (ed.); Thatcher, JW (ed.), Reducibility among combinatorial problems, 85-103 (1972), New York
[17] Kearns, M.: The Computational Complexity of Machine Learning. MIT Press, Cambridge, MA (1990)
[18] Khot, S.; Regev, O., Vertex cover might be hard to approximate to within \[2-\varepsilon 2\]-ε, J. Comput. Syst. Sci., 74, 335-349 (2008) · Zbl 1133.68061
[19] Könemann, J.; Parekh, O.; Segev, D., A uinifed approach to approximating partial covering problems, Algorithmica, 59, 489-509 (2011) · Zbl 1211.68511
[20] Lovász, L., On the ratio of optimal integral and fractional covers, Discrete Math., 13, 383-390 (1975) · Zbl 0323.05127
[21] Manurangsi, P.: Almost-polynomial ratio ETH-hardness of approximating densest \[k\] k-subgraph. In: STOC, pp. 19-23 (2017) · Zbl 1370.68110
[22] Nutov, Z., Approximating Steiner networks with node weights, SIAM J. Comput., 39, 3001-3022 (2010) · Zbl 1217.68248
[23] Nutov, Z., Approximating minimum-cost connectivity problems via uncrossable bifamilies, ACM Trans. Algorithms, 9, 1 (2012) · Zbl 1301.68275
[24] Rajagopalan, S.; Vazirani, V., Primal-dual RNC approximation algorithms for set cover and covering integer programs, SIAM J. Comput., 28, 525-540 (1998) · Zbl 0914.68096
[25] Ran, Y.; Zhang, Z.; Du, H.; Zhu, Y., Approximation algorithm for partial positive influence problem in social network, J. Combin. Optim., 33, 791-802 (2017) · Zbl 1361.90064
[26] Ran, Y.; Shi, Y.; Zhang, Z., Local ratio method on partial set multi-cover, J. Combin. Optim., 34, 302-313 (2017) · Zbl 1383.90034
[27] Ran, Yingli; Shi, Yishuo; Zhang, Zhao, Primal Dual Algorithm for Partial Set Multi-cover, 372-385 (2018), Cham · Zbl 07116393
[28] Slavík, P., Improved performance of the greedy algorithm for partial cover, Inf. Process. Lett., 64, 251-254 (1997) · Zbl 1339.68318
[29] Zhang, Z.; Willson, J.; Lu, Z.; Wu, W.; Zhu, X.; Du, D-Z, Approximating maximum lifetime \[k\] k-coverage through minimizing weighted \[k\] k-cover in homogeneous wireless sensor networks, IEEE/ACM Trans. Netw., 24, 3620-3633 (2016)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.