×

Approximation algorithm for partial set multicover versus full set multicover. (English) Zbl 1434.68681

Summary: In a (full) set multicover (SMC) problem, the goal is to select a subcollection of sets to fully cover all elements, where an element is fully covered if it belongs to at least a required number of sets of the selected subcollection. In a partial set multicover (PSMC) problem, it is sufficient to fully cover a required fraction of elements. In this paper, we present a greedy algorithm for PSMC, and analyze the ratio between the cost of the computed solution and the cost of an optimal solution to the corresponding (full) SMC problem. We shall call this ratio as a partial-versus-full ratio. The motivation for such an analysis is to show that PSMC is fairly economic even when it can only be calculated approximately. It turns out that the partial-versus-full ratio of our algorithm is at most \(\ln \frac{r}{1 - \rho}\), where \(r\) is the requirement of an element, and \(\rho\) is the fraction of elements required to be fully covered. An example is given showing that this ratio is tight up to a constant.

MSC:

68W25 Approximation algorithms
90C27 Combinatorial optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Baryehuda, R., Using homogeneous weights for approximating the partial cover problem, J. Algorithm39(2) (2001) 137-144. · Zbl 0974.68236
[2] Dinur, I. and Steurer, D., Analytical approach to parallel repetition, in STOC Proc. 46th Annual ACM Symp. Theorey of Computing (ACM, NY, 2014), pp. 624-633. · Zbl 1315.91001
[3] Dobson, G., Worst-Case analysis of greedy heuristics for integer programming with nonnegative data, Math. Oper. Res.7(4) (1982) 515-531. · Zbl 0498.90061
[4] Du, D. Z., Ko, K. R. and Hu, X. D., Design and Analysis of Approximation Algorithms (Springer, New York, 2012), pp. 53-54. · Zbl 1237.68009
[5] Feige, U., A threshold of \(\ln n\) for approximating set cover, J. ACM45(4) (1998) 634-652. · Zbl 1065.68573
[6] Gandhi, R., Khuller, S. and Srinivasan, A., Approximation algorithms for partial covering problems, J. Algorithm53(1) (2004) 55-84. · Zbl 1068.68177
[7] Kearns, M. J., The Computational Complexity of Machine Learning (The MIT Press, 1990).
[8] Khot, S. and Regev, O., Vertex cover might be hard to approximate to within \(2 - \varepsilon \), J. Comput. Syst. Sci.74(3) (2008) 335-349. · Zbl 1133.68061
[9] Rajagopalan, S. and Vazirani, V. V., Primal-Dual RNC approximation algorithms for set cover and covering integer programs, SIAM J. Comput.28(2) (1999) 525-540. · Zbl 0914.68096
[10] Ran, Y. L., Shi, Y. S. and Zhang, Z., Local ratio method on partial set multi-cover, J. Comb. Optim.34(1) (2017) 302-313. · Zbl 1383.90034
[11] Ran, Y. L., Zhang, Z., Du, H. W. and Zhu, Y. Q., Approximation algorithm for partial positive influence problem in social network, J. Comb. Optim.33(2) (2017) 791-802. · Zbl 1361.90064
[12] Slavik, P., Improved performance of the greedy algorithm for partial cover, Inform. Process. Lett.64(5) (1997) 251-254. · Zbl 1339.68318
[13] Vazirani, V. V., Approximation Algorithms (Springer, 2001), pp. 112-116.
[14] Wang, F., Camacho, E. and Xu, K., Positive influence dominating set in online social networks, Combinatorial Optimization and Applications. COCOA (Springer, Berlin, 2009), pp. 313-321. · Zbl 1246.91116
[15] Wang, F., Du, H. W., Camacho, E., Xu, K., Lee, W. J., Shi, Y. and Shan, S., On positive influence dominating sets in social networks, Theor. Comput. Sci.412(3) (2011) 265-269. · Zbl 1233.90272
[16] Williamson, D. P. and Shmoys, D. B., The Design of Approximation Algorithms (Cambridge University Press, 2011), pp. 25-26. · Zbl 1219.90004
[17] Zhang, Z., Liu, Q. and Li, D. Y., Two algorithms for connected \(r\)-hop \(k\)-dominating set, Discrete Math. Algorithms Appl.1(04) (2009) 485-498. · Zbl 1184.68649
[18] Zou, F., Willson, J., Zhang, Z. and Wu, W. L., Fast information propagation in social networks, Discrete Math. Algorithms Appl.2(01) (2010) 125-142. · Zbl 1190.91131
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.