Skip to main content
Erschienen in: Journal of Combinatorial Optimization 2/2021

09.01.2021

Approximation algorithm for the multicovering problem

verfasst von: Abbass Gorgi, Mourad El Ouali, Anand Srivastav, Mohamed Hachimi

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 2/2021

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Literatur
Zurück zum Zitat Bar-Yehuda R (2001) Using homogeneous weights for approximating the partial cover problem. J Algorithms 39(2):137–144MathSciNetCrossRef Bar-Yehuda R (2001) Using homogeneous weights for approximating the partial cover problem. J Algorithms 39(2):137–144MathSciNetCrossRef
Zurück zum Zitat Berge C (1973) Graphs and hypergraphs. North-Holland, AmsterdamMATH Berge C (1973) Graphs and hypergraphs. North-Holland, AmsterdamMATH
Zurück zum Zitat Dobson G (1982) Worst-case analysis of greedy heuristics for integer programming with nonnegative data. Math Oper Res 7:515–531MathSciNetCrossRef Dobson G (1982) Worst-case analysis of greedy heuristics for integer programming with nonnegative data. Math Oper Res 7:515–531MathSciNetCrossRef
Zurück zum Zitat 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 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
Zurück zum Zitat El Ouali M, Fohlin H, Srivastav A (2014) A randomised approximation algorithm for the hitting set problem. Theor Comput Sci 555:23–34MathSciNetCrossRef El Ouali M, Fohlin H, Srivastav A (2014) A randomised approximation algorithm for the hitting set problem. Theor Comput Sci 555:23–34MathSciNetCrossRef
Zurück zum Zitat El Ouali M, Munstermann P, Srivastav A (2016b) Randomized approximation for the set multicover problem in hypergraphs. Algorithmica 74:574MathSciNetCrossRef El Ouali M, Munstermann P, Srivastav A (2016b) Randomized approximation for the set multicover problem in hypergraphs. Algorithmica 74:574MathSciNetCrossRef
Zurück zum Zitat Ferdous et al (2017) Parallel algorithms through approximation: b-edge cover. In: IEEE international parallel and distributed processing symposium (IPDPS) Ferdous et al (2017) Parallel algorithms through approximation: b-edge cover. In: IEEE international parallel and distributed processing symposium (IPDPS)
Zurück zum Zitat Ferdous et al (2018) New approximation algorithms for minimum weighted edge cover. SIAM workshop on combinatorial scientific computing (SIAM CSC) Ferdous et al (2018) New approximation algorithms for minimum weighted edge cover. SIAM workshop on combinatorial scientific computing (SIAM CSC)
Zurück zum Zitat 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 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
Zurück zum Zitat Gandhi R, Khuller S, Srinivasan A (2004) Approximation algorithms for partial covering problems. J Algorithms 53(1):55–84MathSciNetCrossRef Gandhi R, Khuller S, Srinivasan A (2004) Approximation algorithms for partial covering problems. J Algorithms 53(1):55–84MathSciNetCrossRef
Zurück zum Zitat Hall NG, Hochbaum DS (1986) A fast approximation algorithm for the multicovering problem. Discrete Appl Math 15:35–40MathSciNetCrossRef Hall NG, Hochbaum DS (1986) A fast approximation algorithm for the multicovering problem. Discrete Appl Math 15:35–40MathSciNetCrossRef
Zurück zum Zitat Hochbaum DS (1982) Approximation algorithms for the set covering and vertex cover problems. SIAM J Comput 11(3):555–556MathSciNetCrossRef Hochbaum DS (1982) Approximation algorithms for the set covering and vertex cover problems. SIAM J Comput 11(3):555–556MathSciNetCrossRef
Zurück zum Zitat 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 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
Zurück zum Zitat Khot S, Regev O (2008) Vertex cover might be hard to approximate to within 2-epsilon. J Comput Syst Sci 74(3):335–349CrossRef Khot S, Regev O (2008) Vertex cover might be hard to approximate to within 2-epsilon. J Comput Syst Sci 74(3):335–349CrossRef
Zurück zum Zitat 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 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
Zurück zum Zitat McDiarmid C (1989) On the method of bounded differences. Surveys in combinatorics (Norwich 1989). Cambridge University Press, Cambridge, pp 148–188CrossRef McDiarmid C (1989) On the method of bounded differences. Surveys in combinatorics (Norwich 1989). Cambridge University Press, Cambridge, pp 148–188CrossRef
Zurück zum Zitat Motwani R, Raghavan P (1995) Randomized algorithms. Cambridge University Press, CambridgeCrossRef Motwani R, Raghavan P (1995) Randomized algorithms. Cambridge University Press, CambridgeCrossRef
Zurück zum Zitat Peleg D, Schechtman G, Wool A (1997) Randomized approximation of bounded multicovering problems. Algorithmica 18(1):44–66MathSciNetCrossRef Peleg D, Schechtman G, Wool A (1997) Randomized approximation of bounded multicovering problems. Algorithmica 18(1):44–66MathSciNetCrossRef
Zurück zum Zitat Vazirani VV (2001) Approximation algorithms. Springer, Berlin, pp 112–116 Vazirani VV (2001) Approximation algorithms. Springer, Berlin, pp 112–116
Metadaten
Titel
Approximation algorithm for the multicovering problem
verfasst von
Abbass Gorgi
Mourad El Ouali
Anand Srivastav
Mohamed Hachimi
Publikationsdatum
09.01.2021
Verlag
Springer US
Erschienen in
Journal of Combinatorial Optimization / Ausgabe 2/2021
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI
https://doi.org/10.1007/s10878-020-00688-9

Weitere Artikel der Ausgabe 2/2021

Journal of Combinatorial Optimization 2/2021 Zur Ausgabe