An approximation algorithm for the partial vertex cover problem in hypergraphs

详细信息    查看全文

• 作者：Mourad El Ouali ; Helena Fohlin ; Anand Srivastav
• 关键词：Combinatorial optimization ; Approximation algorithms ; Hypergraphs ; Vertex cover ; Probabilistic methods
• 刊名：Journal of Combinatorial Optimization
• 出版年：2016
• 出版时间：February 2016
• 年：2016
• 卷：31
• 期：2
• 页码：846-864
• 全文大小：477 KB
• 参考文献：Alon N, Moshkovitz D, Safra S (2006) Algorithmic construction of sets for \(k\) -restrictions. ACM Trans Algorithms 2:153–177MathSciNet CrossRef
  Angluin D, Valiant LG (1979) Fast probabilistic algorithms for Hamiltonion circuits and matchings. J Comput Syst Sci 18:155–193MathSciNet CrossRef MATH
  Alon N, Spencer J (2000) The probabilistic method, 2nd edn. Wiley Interscience, Hoboken, NJCrossRef MATH
  Berge C (1989) Hypergraphs- combinatorics of finite sets. North Holland Mathematical Library
  Chvátal V (1979) A greedy heuristic for the set covering problem. OMEGA 4(3):233–235MATH
  Duh R, Fürer M (1997) Approximating \(k\) -set cover by semi-local optimization. In: Proceedings of the 29th annual ACM symposium on theory of computing (STOC ’97), pp 256–264, May
  Feige U (1998) A treshold of \(\ln n\) for approximating set cover. J ACM 45(4):634–652MathSciNet CrossRef MATH
  Feige U, Langberg M (2001) Approximation algorithms for maximization problems arising in graph partitioning. J Algorithms 41(2):174–201MathSciNet CrossRef MATH
  Frieze A, Jerrum M (1997) Improved approximation algorithms for max \(k\) -cut and max bisection. Algorithmica 18:67–81MathSciNet CrossRef MATH
  Gandhi R, Khuller S, Srinivasan A (2004) Approximation algorithms for partial covering problems. J Algorithms 53(1):55–84MathSciNet CrossRef MATH
  Halperin E (2000) Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. ACM-SIAM Symp Discret Algorithms 11:329–337MathSciNet
  Halperin E, Srinivasan A (2002) Improved approximation algorithms for the partial vertex cover problem. In: 5th international workshop on approximation algorithms for combinatorial optimization problems, LNCS, vol 2462, pp 161–174
  Hochbaum DS (1982) Approximation algorithms for the set covering and vertex cover problems. SIAM J Comput 11(3):555–556MathSciNet CrossRef MATH
  Jäger G, Srivastav A (2005) Improved approximation algorithms for maximum graph partitioning problems. J Comb Optim 10(2):133–167MathSciNet CrossRef MATH
  Karmarkar N (1984) A new polynomial time algorithm for linear programming. Combinatorica 4(4):373–395MathSciNet CrossRef MATH
  Khachian LG (1979) A polynomial algorithm in linear programming [in Russian]. Doklady Akademii Nauk SSSR 244: 1093–1096, 1979. English translation: Soviet Mathematics Doklady 20: 191–194
  Khot S, Regev O (2008) Vertex cover might be hard to approximate to within 2-epsilon. J Comput Syst Sci 74(3):335–349MathSciNet CrossRef MATH
  Krivelevich J (1997) Approximate set covering in uniform hypergraphs. J Algorithms 25(1):118–143MathSciNet CrossRef MATH
  Lovász L (1975) On the ratio of optimal integral and fractional covers. Discrete Math 13:383–390MathSciNet CrossRef MATH
  Lund C, Yannakakis M (1994) On the hardness of approximating minimization problems. J Assoc Comput Mach 41:960–981MathSciNet CrossRef MATH
  Matousek J (2010) Geometric discrepancy. Algorithms and combinatorics. Springer, Berlin
  Matousek J, Wagner U (2004) New constructions of weak epsilon-nets. Discret Comput Geom 32(2):195–206MathSciNet CrossRef MATH
  McDiarmid C (1989) On the method of bounded differences. Surveys in combinatorics (Norwich, 1989), pp 148–188. Cambridge University Press, Cambridge
  Motwani R, Raghavan P (1995) Randomized algorithms. Cambridge University Press, CambridgeCrossRef MATH
  Peleg D, Schechtman G, Wool A (1997) Randomized approximation of bounded multicovering problems. Algorithmica 18(1):44–66MathSciNet CrossRef MATH
  Raz R Safra S (1997) A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In: Proceedings 29th ACM symposium on theory of computing, pp 475–484
  
• 作者单位：Mourad El Ouali (1)
  Helena Fohlin (2)
  Anand Srivastav (1)
  
  1. Department of Computer Science, University of Kiel, Kiel, Germany
  2. Department of Clinical and Experimental Medicine, Linköping University, Linköping, Sweden
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Convex and Discrete Geometry
  Mathematical Modeling and IndustrialMathematics
  Theory of Computation
  Optimization
  Operation Research and Decision Theory
  
• 出版者：Springer Netherlands
• ISSN：1573-2886

文摘

Let \(\mathcal {H}=(V,\mathcal {E})\) be a hypergraph with set of vertices \(V, n:=|V|\) and set of (hyper-)edges \(\mathcal {E}, m:=|\mathcal {E}|\). Let \(l\) be the maximum size of an edge, \(\varDelta \) be the maximum vertex degree and \(D\) be the maximum edge degree. The \(k\)-partial vertex cover problem in hypergraphs is the problem of finding a minimum cardinality subset of vertices in which at least \(k\) hyperedges are incident. For the case of \(k=m\) and constant \(l\) it known that an approximation ratio better than \(l\) cannot be achieved in polynomial time under the unique games conjecture (UGC) (Khot and Ragev J Comput Syst Sci, 74(3):335–349, 2008), but an \(l\)-approximation ratio can be proved for arbitrary \(k\) (Gandhi et al. J Algorithms, 53(1):55–84, 2004). The open problem in this context has been to give an \(\alpha l\)-ratio approximation with \(\alpha < 1\), as small as possible, for interesting classes of hypergraphs. In this paper we present a randomized polynomial-time approximation algorithm which not only achieves this goal, but whose analysis exhibits approximation phenomena for hypergraphs with \(l\ge 3\) not visible in graphs: if \(\varDelta \) and \(l\) are constant, and \(2\le l\le 4\varDelta \), we prove for \(l\)-uniform hypergraphs a ratio of \(l\left( 1-\frac{l-1}{4\varDelta }\right) \), which tends to the optimal ratio 1 as \(l\ge 3\) tends to \(4\varDelta \). For the larger class of hypergraphs where \(l, l \ge 3\), is not constant, but \(D\) is a constant, we show a ratio of \(l(1-1/6D)\). Finally for hypergraphs with non-constant \(l\), but constant \(\varDelta \), we get a ratio of \( l (1- \frac{2 - \sqrt{3}}{6\varDelta })\) for \(k\ge m/4\), leaving open the problem of finding such an approximation for \(k < m/4\). Keywords Combinatorial optimization Approximation algorithms Hypergraphs Vertex cover Probabilistic methods