A Randomised Approximation Algorithm for the Hitting Set Problem

详细信息    查看全文

• 作者：Mourad El Ouali (18)
  Helena Fohlin (19)
  Anand Srivastav (18)
  
• 关键词：Approximation algorithms ; probabilistic methods ; randomised rounding ; hitting set ; vertex cover ; greedy
• 刊名：Lecture Notes in Computer Science
• 出版年：2013
• 出版时间：2013
• 年：2013
• 卷：7748
• 期：1
• 页码：114-125
• 全文大小：264KB
• 参考文献：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., Even, S.: A linear-time approximation algorithm for the weighted vertex cover problem. Journal of Algorithms?2, 198-03 (1981) CrossRef
  4. Bar-Yehuda, R., Even, S.: A local ratio theorem for approximating weighted vertex cover problem. In: Ausiello, G., Lucertini, M. (eds.) Analysis and Design of Algorithms for Combinatorial Problems. Annals of Discrete Math., vol.?25, pp. 27-6. Elsevier, Amsterdam (1985) CrossRef
  5. Berge, C.: Hypergraphs-combinatorics of finite sets. North Holland Mathematical Library (1989)
  6. Chvatal, V.: A greedy heuristic for the set covering problem. Math. Oper. Res.?4(3), 233-35 (1979) CrossRef
  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. Füredi, Z.: Matchings and covers in hypergraphs. Graphs and Combinatorics?4(1), 115-06 (1988) CrossRef
  11. Gandhi, R., Khuller, S., Srinivasan, A.: Approximation Algorithms for Partial Covering Problems. J. Algorithms?53(1), 55-4 (2004) CrossRef
  12. 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)
  13. Hochbaum, D.S.: Approximation algorithms for the set covering and vertex cover problems. SIAM J. Computation?11(3), 555-56 (1982) CrossRef
  14. Hall, N.G., Hochbaum, D.S.: A fast approximation for the multicovering problem. Discrete Appl. Math.?15, 35-0 (1986) CrossRef
  15. J?ger, G., Srivastav, A.: Improved approximation algorithms for maximum graph partitioning problems. Journal of Combinatorial Optimization?10(2), 133-67 (2005) CrossRef
  16. Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. System Sci.?9, 256-78 (1974) CrossRef
  17. 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
  18. Krivelevich, J.: Approximate set covering in uniform hypergraphs. J. Algorithms?25(1), 118-43 (1997) CrossRef
  19. Lovász, L.: On the ratio of optimal integral and fractional covers. Discrete Math.?13, 383-90 (1975) CrossRef
  20. Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. J. Assoc. Comput. Mach.?41, 960-81 (1994) CrossRef
  21. McDiarmid, C.: Concentration. In: Habib, M., McDiarmid, C., Ramirez-Alfonsin, J., Reed, B. (eds.) Probabilistic Methods for Algorithmic Discrete Mathematics, pp. 195-48. Springer, Berlin (1998) CrossRef
  22. Peleg, D., Schechtman, G., Wool, A.: Randomized approximation of bounded multicovering problems. Algorithmica?18(1), 44-6 (1997) CrossRef
  23. Okun, M.: On approximation of the vertex cover problem in hypergraphs. Discrete Optimization (DISOPT)?2(1), 101-11 (2005) CrossRef
  24. 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. Departement of Computer Science, University of Kiel, Germany
  19. Department of Clinical and Experimental Medicine, Link?ping University, Sweden
  
• ISSN：1611-3349

文摘

Let $\mathcal{H}=(V,\mathcal{E})$ be a hypergraph with vertex set V and edge set $\mathcal{E} $ , where n :-?|V| and $m := |{\cal E}|$ . Let l be the maximum size of an edge and Δ be the maximum vertex degree. A hitting set (or vertex cover) in $\mathcal{H}$ is a set of vertices from V in which all edges are incident. The hitting set problem is to find a hitting set of minimum cardinality. It is known that an approximation ratio of l can be achieved easily. On the other side, for constant l, an approximation ratio better than l cannot be achieved in polynomial time under the unique games conjecture (Khot and Ragev 2008). Thus breaking the l-barrier for significant classes of hypergraphs is a complexity-theoretic and algorithmically interesting problem, which has been studied by several authors (Krivelevich (1997), Halperin (2000), Okun (2005)). We propose a randomised algorithm of hybrid type for the hitting set problem, which combines LP-based randomised rounding, graphs sparsening and greedy repairing and analyse it in different environments. For hypergraphs with $\Delta = O(n^{\frac14})$ and $l=O(\sqrt{n})$ we achieve an approximation ratio of $l\left(1-\frac{c}{\Delta}\right)$ , for some constant c-gt;-, with constant probability. In the case of l-uniform hypergraphs, l and Δ being constants, we prove by analysing the expected size of the hitting set and using concentration inequalities, a ratio of $l\left(1-\frac{l-1}{4\Delta}\right)$ . Moreover, for quasi-regularisable hypergraphs, we achieve an approximation ratio of $l\left(1-\frac{n}{8m}\right)$ . We show how and when our results improve over the results of Krivelevich, Halperin and Okun.