Randomized Approximation for the Set Multicover Problem in Hypergraphs

详细信息    查看全文

• 作者：Mourad El Ouali ; Peter Munstermann ; Anand Srivastav
• 关键词：Combinatorial optimization ; Approximation algorithms ; Randomized algorithm ; Hypergraphs ; Set cover and set multicover
• 刊名：Algorithmica
• 出版年：2016
• 出版时间：February 2016
• 年：2016
• 卷：74
• 期：2
• 页码：574-588
• 全文大小：440 KB
• 参考文献：1.Alon, N., Spencer, J.: The Probabilistic Method, 2nd edn. Wiley, New York (2000)CrossRef MATH
  2.Bar-Yehuda, R.: Using homogeneous weights for approximating the partial cover problem. J. Algorithms 39(2), 137–144 (2001)CrossRef MathSciNet MATH
  3.Berman, P., DasGupta, B., Sontag, E.: Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks. Discrete Appl. Math. 155(6–7), 733–749 (2007)CrossRef MathSciNet MATH
  4.Chvátal, V.: A greedy heuristic for the set covering problem. Math. Oper. Res. 4(3), 233–235 (1979)CrossRef MathSciNet MATH
  5.El Ouali, M., Fohlin, H., Srivastav, A.: An Approximation Algorithm for the Partial Vertex Cover Problem in Hypergraphs. J. Comb. Optim. (2014). doi:10.​1007/​s10878-014-9793-2
  6.El Ouali, M., Fohlin, H., Srivastav, A.: A randomised approximation algorithm for the hitting set problem. Theor. Comput. Sci. 555, 23–34 (2014)CrossRef MATH
  7.Feige, U., Langberg, M.: Approximation algorithms for maximization problems arising in graph partitioning. J. Algorithms 41(2), 174–201 (2001)CrossRef MathSciNet MATH
  8.Frieze, A., Jerrum, M.: Improved Approximation Algorithms for MAX \(k\) -CUT and MAX BISECTION. Algorithmica 18, 67–81 (1997)CrossRef MathSciNet MATH
  9.Gandhi, R., Khuller, S., Srinivasan, A.: Approximation algorithms for partial covering problems. J. Algorithms 53(1), 55–84 (2004)CrossRef MathSciNet MATH
  10.Habib, M., McDiarmid, C., Ramirez-Alfonsin, J., Reed, B.: Probabilistic Methods for Algorithmic Discrete Mathematics, pp. 195–248. Springer Berlin Heidelberg (1998)
  11.Hall, N.G., Hochbaum, D.S.: A fast approximation algorithm for the multicovering problem. Discrete Appl. Math. 15, 35–40 (1986)CrossRef MathSciNet MATH
  12.Halperin, E.: Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. SIAM J. Comput. 31(5), 1608–1623 (2002)CrossRef MathSciNet MATH
  13.Hochbaum, D.S.: Approximation algorithms for the set covering and vertex cover problems. SIAM J. Comput. 11(3), 555–556 (1982)CrossRef MathSciNet MATH
  14.Jäger, G., Srivastav, A.: Improved approximation algorithms for maximum graph partitioning problems. J. Comb. Optim. 10(2), 133–167 (2005)CrossRef MathSciNet MATH
  15.Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9, 256–278 (1974)CrossRef MATH
  16.Krivelevich, J.: Approximate set covering in uniform hypergraphs. J. Algorithms 25(1), 118–143 (1997)CrossRef MathSciNet MATH
  17.Lovász, L.: On the ratio of optimal integral and fractional covers. Discrete Math. 13(4), 383–390 (1975)CrossRef MathSciNet MATH
  18.Peleg, D., Schechtman, G., Wool, A.: Randomized approximation of bounded multicovering problems. Algorithmica 18(1), 44–66 (1997)CrossRef MathSciNet MATH
  19.Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2-epsilon. J. Comput. Syst. Sci. 74(3), 335–349 (2008)CrossRef MathSciNet MATH
  20.Vazirani, V.V.: Approximation Algorithms. Springer, Berlin (2003)CrossRef
  
• 作者单位：Mourad El Ouali (1)
  Peter Munstermann (1)
  Anand Srivastav (1)
  
  1. Department of Computer Science, Christian-Albrechts-Universität, 24118, Kiel, Germany
  
• 刊物类别：Computer Science
• 刊物主题：Algorithm Analysis and Problem Complexity
  Theory of Computation
  Mathematics of Computing
  Algorithms
  Computer Systems Organization and Communication Networks
  Data Structures, Cryptology and Information Theory
  
• 出版者：Springer New York
• ISSN：1432-0541

文摘

Let \(b\in {\mathbb {N}}_{\ge 1}\) and let \({\mathcal {H}}=(V,{\mathcal {E}})\) be a hypergraph with maximum vertex degree \({\varDelta }\) and maximum edge size \(l\). A set \(b\)-multicover in \({\mathcal {H}}\) is a set of edges \(C \subseteq {\mathcal {E}}\) such that every vertex in \(V\) belongs to at least \(b\) edges in \(C\). \({\textsc {set }}\, b\text {-}{\textsc {multicover}}\) is the problem of finding a set \(b\)-multicover of minimum cardinality, and for \(b=1\) it is the fundamental set cover problem. Peleg et al. (Algorithmica 18(1):44–66, 1997) gave a randomized algorithm achieving an approximation ratio of \(\delta \cdot \big (1-\big (\frac{c}{n}\big )^\frac{1}{\delta }\big )\), where \(\delta := {\varDelta }- b + 1\) and \(c>0\) is a constant. As this ratio depends on the instance size \(n\) and tends to \(\delta \) as \(n\) tends to \(\infty \), it remained an open problem whether an approximation ratio of \(\delta \alpha \) with a constant \(\alpha < 1\) can be proved. In fact, the authors conjectured that for any fixed \({\varDelta }\) and \(b\), the problem is not approximable within a ratio smaller than \(\delta \), unless \({\mathcal {P}}={\mathcal {NP}}\). We present a randomized algorithm of hybrid type for \({\textsc {set }}\, b\text {-}{\textsc {multicover}}\), \(b \ge 2\), combining LP-based randomized rounding with greedy repairing, and achieve an approximation ratio of \(\delta \cdot \left( 1 - \frac{11({\varDelta }- b)}{72l} \right) \) for hypergraphs with maximum edge size \(l \in {\mathcal {O}}\left( \max \big \{(nb)^\frac{1}{5},n^\frac{1}{4}\big \}\right) \). In particular, for all hypergraphs where \(l\) is constant, we get an \(\alpha \delta \)-ratio with constant \(\alpha < 1\). Hence the above stated conjecture does not hold for hypergraphs with constant \(l\) and we have identified the boundedness of the maximum hyperedge size as a relevant parameter responsible for approximations below \(\delta \). Keywords Combinatorial optimization Approximation algorithms Randomized algorithm Hypergraphs Set cover and set multicover