# 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
Full Text:
##### References:
  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  Bar-Yuhuda, R., Using homogeneous weights for approximating the partial cover problem, J. Algorithms, 39, 137-144 (2001) · Zbl 0974.68236  Bar-Yuhuda, R.; Even, S., A local-ratio theorem for approximating the weighted vertex cover problem, N.-Holl. Math. Stud., 109, 27-45 (1985)  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  Chekuri, Chandra; Ene, Alina; Vakilian, Ali, Prize-Collecting Survivable Network Design in Node-Weighted Graphs, 98-109 (2012), Berlin, Heidelberg · Zbl 1372.68206  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  Chvatal, V., A greedy heuristic for the set-covering problem, Math. Oper. Res., 4, 233-235 (1979) · Zbl 0443.90066  Dinur, I.; Steurer, D., Analytical approach to parallel repetition, STOC, 2014, 624-633 (2014) · Zbl 1315.91001  Dobson, G., Worst-case analysis of greedy heuristics for integer programming with nonnegatice data, Math. Oper. Res., 7, 515-531 (1982) · Zbl 0498.90061  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  Gandhi, R.; Khuller, S.; Srinivasan, A., Approximation algorithms for partial covering problems, J. Algorithms, 53, 55-84 (2004) · Zbl 1068.68177  Hajiaghayi, M.; Khandekar, R.; Kortsarz, G.; Nutov, Z., Prize-collecting Steiner network problems, IPCO, 2010, 71-84 (2010) · Zbl 1285.90049  Hochbaum, DS, Approximation algorithms for the set covering and vertex cover problems, SIAM J. Comput., 11, 555-556 (1982) · Zbl 0486.68067  Ignizio, J.P., Cavalier, T.M.: Linear Programming. Prentice-Hall, Inc., Upper Saddle River (1994)  Johnson, DS, Approximation algorithms for combinatorial problems, J. Comput. Syst Sci., 9, 256-278 (1974) · Zbl 0296.65036  Karp, RM; Miller, RE (ed.); Thatcher, JW (ed.), Reducibility among combinatorial problems, 85-103 (1972), New York  Kearns, M.: The Computational Complexity of Machine Learning. MIT Press, Cambridge, MA (1990)  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  Könemann, J.; Parekh, O.; Segev, D., A uinifed approach to approximating partial covering problems, Algorithmica, 59, 489-509 (2011) · Zbl 1211.68511  Lovász, L., On the ratio of optimal integral and fractional covers, Discrete Math., 13, 383-390 (1975) · Zbl 0323.05127  Manurangsi, P.: Almost-polynomial ratio ETH-hardness of approximating densest $k$ k-subgraph. In: STOC, pp. 19-23 (2017) · Zbl 1370.68110  Nutov, Z., Approximating Steiner networks with node weights, SIAM J. Comput., 39, 3001-3022 (2010) · Zbl 1217.68248  Nutov, Z., Approximating minimum-cost connectivity problems via uncrossable bifamilies, ACM Trans. Algorithms, 9, 1 (2012) · Zbl 1301.68275  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  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  Ran, Y.; Shi, Y.; Zhang, Z., Local ratio method on partial set multi-cover, J. Combin. Optim., 34, 302-313 (2017) · Zbl 1383.90034  Ran, Yingli; Shi, Yishuo; Zhang, Zhao, Primal Dual Algorithm for Partial Set Multi-cover, 372-385 (2018), Cham · Zbl 07116393  Slavík, P., Improved performance of the greedy algorithm for partial cover, Inf. Process. Lett., 64, 251-254 (1997) · Zbl 1339.68318  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.