A Randomised Approximation Algorithm for the Hitting Set Problem
详细信息    查看全文
文摘
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.

© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号

地址：北京市海淀区学院路29号 邮编：100083

电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700