A Randomised Approximation Algorithm for the Partial Vertex Cover Problem in Hypergraphs

详细信息    查看全文

• 作者：Mourad El Ouali (18)
  Helena Fohlin (19)
  Anand Srivastav (18)
  
• 关键词：Combinatorial optimization ; approximation algorithms ; hypergarphs ; vertex cover ; probabilistic methods
• 刊名：Lecture Notes in Computer Science
• 出版年：2012
• 出版时间：2012
• 年：2012
• 卷：7659
• 期：1
• 页码：188-202
• 全文大小：267KB
• 参考文献：1. Alon, N., Moshkovitz, D., Safra, S.: Algorithmic construction of sets for / k-restrictions. ACM Trans. Algorithms (ACM)?2, 153-77 (2006) CrossRef
  2. Alon, N., Spencer, J.: The probabilistic method, 2nd edn. Wiley Interscience (2000)
  3. Bar-Yehuda, R.: Using homogeneous weights for approximating the partial cover problem. Journal of Algorithms?39(2), 137-44 (2001) CrossRef
  4. Berge, C.: Hypergraphs- combinatorics of finite sets. North Holland Mathematical Library (1989)
  5. Chvátal, V.: A greedy heuristic for the set covering problem. Math. Oper. Res.?4(3), 233-35 (1979) CrossRef
  6. Duh, R., Fürer, M.: Approximating / k-set cover by semi-local optimization. In: Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC 1997), pp. 256-64 (May 1997)
  7. Feige, U.: A treshold of ln / n for approximating set cover. Journal of the ACM?45(4), 634-52 (1998) CrossRef
  8. Feige, U., Langberg, M.: Approximation algorithms for maximization problems arising in graph partitioning. Journal of Algorithms?41(2), 174-01 (2001) CrossRef
  9. Frieze, A., Jerrum, M.: Improved approximation algorithms for max / k-cut and max bisection. Algorithmica?18, 67-1 (1997) CrossRef
  10. Gandhi, R., Khuller, S., Srinivasan, A.: Approximation Algorithms for Partial Covering Problems. J. Algorithms?53(1), 55-4 (2004) CrossRef
  11. Halperin, E.: Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. In: ACM-SIAM Symposium on Discrete Algorithms, vol.?11, pp. 329-37 (2000)
  12. Halperin, E., Srinivasan, A.: Improved Approximation Algorithms for the Partial Vertex Cover Problem. In: Jansen, K., Leonardi, S., Vazirani, V.V. (eds.) APPROX 2002. LNCS, vol.?2462, pp. 161-74. Springer, Heidelberg (2002) CrossRef
  13. Hochbaum, D.S.: Approximation algorithms for the set covering and vertex cover problems. SIAM J. Computation?11(3), 555-56 (1982) CrossRef
  14. J?ger, G., Srivastav, A.: Improved approximation algorithms for maximum graph partitioning problems. Journal of Combinatorial Optimization?10(2), 133-67 (2005) CrossRef
  15. Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2-epsilon. J. Comput. Syst. Sci.?74(3), 335-49 (2008) CrossRef
  16. Krivelevich, J.: Approximate set covering in uniform hypergraphs. J. Algorithms?25(1), 118-43 (1997) CrossRef
  17. Lovász, L.: On the ratio of optimal integral and fractional covers. Discrete Math.?13, 383-90 (1975) CrossRef
  18. Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. J. Assoc. Comput. Mach.?41, 960-81 (1994) CrossRef
  19. Matousek, J.: Geometric Discrepancy. Algorithms and Combinatorics, vol.?18. Springer, Heidelberg (2010) CrossRef
  20. Matousek, J., Wagner, U.: New Constructions of Weak epsilon-Nets. Discrete & Computational Geometry?32(2), 195-06 (2004) CrossRef
  21. McDiarmid, C.: On the method of bounded differences. Surveys in Combinatorics, Norwich, pp. 148-88. Cambridge Univ. Press, Cambridge (1989)
  22. Peleg, D., Schechtman, G., Wool, A.: Randomized approximation of bounded multicovering problems. Algorithmica?18(1), 44-6 (1997) CrossRef
  23. Raz, R., Safra, S.: A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In: Proc. 29th ACM Symp. on Theory of Computing, pp. 475-84 (1997)
  
• 作者单位：Mourad El Ouali (18)
  Helena Fohlin (19)
  Anand Srivastav (18)
  
  18. Department of Computer Science, University of Kiel, Germany
  19. Department of Clinical and Experimental Medicine, Link?ping University, Sweden
  
• ISSN：1611-3349

文摘

In this paper we present an approximation algorithm for the k-partial vertex cover problem in hypergraphs. Let $\mathcal{H}=(V,\mathcal{E})$ be a hypergraph with set of vertices V, |V|--em class="a-plus-plus">n and set of (hyper-)edges $|\mathcal{E}|, |\mathcal{E}| =m$ . 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. It is a generalisation of the fundamental (partial) vertex cover problem in graphs and the hitting set problem in hypergraphs. Let l, l?≥- be the maximum size of an edge, Δ be the maximum vertex degree and D be maximum edge degree. For a constant l, l?≥- a non-approximabilty result is known: an approximation ratio better than l cannot be achieved in polynomial-time under the unique games conjecture (Khot and Rageev 2003, 2008). On the other hand, with the primal-dual method (Gandhi, Khuller, Srinivasan 2001) and the local-ratio method (Bar-Yehuda 2001), the l-approximation ratio can be proved. Thus approximations below the l-ratio for large classes of hypergraphs, for example those with constant D or Δ are interesting. In case of graphs (l--) such results are known. In this paper we break the l-approximation barrier for hypergraph classes with constant D resp. Δ for the partial vertex cover problem in hypergraphs. We propose a randomised algorithm of hybrid type which combines LP-based randomised rounding and greedy repairing. For hypergraphs with arbitrary l, l?≥-, and constant D the algorithm achieves an approximation ratio of l(1???ο1/(D--))), and this can be improved to l (1???ο1/Δ)) if Δ is constant and k?≥-em class="a-plus-plus">m/4. For the class of l-uniform hypergraphs with both l and Δ being constants and l?≤-Δ, we get a further improvement to a ratio of $l\left(1-\frac{l-1}{4\Delta}\right)$ . The analysis relies on concentration inequalities and combinatorial arguments.