Abstract
Let \(\mathcal {H}=(V,\mathcal {E})\) be a hypergraph with maximum edge size \(\ell \) and maximum degree \(\varDelta \). For a given positive integers \(b_v\), \(v\in V\), a set multicover in \(\mathcal {H}\) is a set of edges \(C \subseteq \mathcal {E}\) such that every vertex v in V belongs to at least \(b_v\) edges in C. Set multicover is the problem of finding a minimum-cardinality set multicover. Peleg, Schechtman and Wool conjectured that for any fixed \(\varDelta \) and \(b:=\min _{v\in V}b_{v}\), the problem of set multicover is not approximable within a ratio less than \(\delta :=\varDelta -b+1\), unless \(\mathcal {P}=\mathcal {NP}\). Hence it’s a challenge to explore for which classes of hypergraph the conjecture doesn’t hold. We present a polynomial time algorithm for the set multicover problem which combines a deterministic threshold algorithm with conditioned randomized rounding steps. Our algorithm yields an approximation ratio of \(\max \left\{ \frac{148}{149}\delta , \left( 1- \frac{ (b-1)e^{\frac{\delta }{4}}}{94\ell } \right) \delta \right\} \) for \(b\ge 2\) and \(\delta \ge 3\). Our result not only improves over the approximation ratio presented by El Ouali et al. (Algorithmica 74:574, 2016) but it’s more general since we set no restriction on the parameter \(\ell \). Moreover we present a further polynomial time algorithm with an approximation ratio of \(\frac{5}{6}\delta \) for hypergraphs with \(\ell \le (1+\epsilon )\bar{\ell }\) for any fixed \(\epsilon \in [0,\frac{1}{2}]\), where \(\bar{\ell }\) is the average edge size. The analysis of this algorithm relies on matching/covering duality due to Ray-Chaudhuri (1960), which we convert into an approximative form. The second performance disprove the conjecture of Peleg et al. for a large subclass of hypergraphs.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bar-Yehuda R (2001) Using homogeneous weights for approximating the partial cover problem. J Algorithms 39(2):137–144
Berge C (1973) Graphs and hypergraphs. North-Holland, Amsterdam
Chvatal V (1979) A greedy heuristic for the set-covering problem. Math Oper Res 4:233–235
Dobson G (1982) Worst-case analysis of greedy heuristics for integer programming with nonnegative data. Math Oper Res 7:515–531
Duh R, Fürer M (1997) Approximating k-set cover by semi-local optimization. In: Proceedings of 29th annual symposium on theory on computing, May, pp 256–264
El Ouali M, Fohlin H, Srivastav A (2014) A randomised approximation algorithm for the hitting set problem. Theor Comput Sci 555:23–34
El Ouali M, Fohlin H, Srivastav A (2016a) An approximation algorithm for the partial vertex cover problem in hypergraphs. J Comb Optim 31:846. https://doi.org/10.1007/s10878-014-9793-2
El Ouali M, Munstermann P, Srivastav A (2016b) Randomized approximation for the set multicover problem in hypergraphs. Algorithmica 74:574
Ferdous et al (2017) Parallel algorithms through approximation: b-edge cover. In: IEEE international parallel and distributed processing symposium (IPDPS)
Ferdous et al (2018) New approximation algorithms for minimum weighted edge cover. SIAM workshop on combinatorial scientific computing (SIAM CSC)
Fujito T, Kurahashi H (2005) A better-than-greedy algorithm for k-set multicover. In: Erlebach T, Persinao G (eds) Approximation and online algorithms. WAOA. Lecture notes in computer science, vol 3879. Springer, Berlin
Gandhi R, Khuller S, Srinivasan A (2004) Approximation algorithms for partial covering problems. J Algorithms 53(1):55–84
Hall NG, Hochbaum DS (1986) A fast approximation algorithm for the multicovering problem. Discrete Appl Math 15:35–40
Hochbaum DS (1982) Approximation algorithms for the set covering and vertex cover problems. SIAM J Comput 11(3):555–556
Johnson DS (1974) Approximation algorithms for combinatorial problems. J Comput Syst Sci 9:256–278
Karp RM (1972) Reducibility among combinatorial problems. In: Miller RE, Thatcher JW, Bohlinger JD (eds) Complexity of computer computations. The IBM research symposia series. Springer, Boston
Khot S, Regev O (2008) Vertex cover might be hard to approximate to within 2-epsilon. J Comput Syst Sci 74(3):335–349
Koufogiannakis C, Young NE (2013) Greedy \(\Delta \)-approximation algorithm for covering with arbitrary constraints and submodular cost. Algorithmica 66:113. https://doi.org/10.1007/s00453-012-9629-3
Krysta P (2005) Greedy approximation via duality for packing, combinatorial auctions and routing. In: Jedrzejowicz J, Szepietowski A (eds) Mathematical foundations of computer science (2005) MFCS 2005, vol 3618. Lecture notes in computer science. Springer, Berlin
Lovász L (1975) On the ratio of optimal integral and fractional covers. Discrete Math 13(4):383–390
McDiarmid C (1989) On the method of bounded differences. Surveys in combinatorics (Norwich 1989). Cambridge University Press, Cambridge, pp 148–188
Motwani R, Raghavan P (1995) Randomized algorithms. Cambridge University Press, Cambridge
Peleg D, Schechtman G, Wool A (1993) Approximating bounded 0–1 integer linear programs. In: Proceedings of 2nd Israel symposium on theory of computing and systems, pp 69–77. https://doi.org/10.1109/ISTCS.1993.253482
Peleg D, Schechtman G, Wool A (1997) Randomized approximation of bounded multicovering problems. Algorithmica 18(1):44–66
Vazirani VV (2001) Approximation algorithms. Springer, Berlin, pp 112–116
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Gorgi, A., El Ouali, M., Srivastav, A. et al. Approximation algorithm for the multicovering problem. J Comb Optim 41, 433–450 (2021). https://doi.org/10.1007/s10878-020-00688-9
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-020-00688-9