El Ouali, Mourad, Fohlin, Helena and Srivastav, Anand (2014) A randomised approximation algorithm for the hitting set problem. Theoretical Computer Science, 555 . pp. 23-34. DOI 10.1016/j.tcs.2014.03.029.

Full text not available from this repository.

Abstract

Let H = (V, epsilon) be a hypergraph with vertex set V and edge set epsilon, where n := vertical bar V vertical bar and m := vertical bar epsilon vertical bar. Let l be the maximum size of an edge and Delta be the maximum vertex degree. A hitting set (or vertex cover) in H is a subset of 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 hand, for constant l, an approximation ratio better than l cannot be achieved in polynomial time under the unique games conjecture (Khot and Regev, 2008 [17]). Thus breaking the l-barrier for significant classes of hypergraphs is a complexity-theoretically and algorithmically interesting problem, which has been studied by several authors (Krivelevich, 1997 [18], Halperin, 2000 [12], Okun, 2005 [23]). 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 for different classes of hypergraphs. For hypergraphs with Delta = O(n1/4) and l = O (root n) we achieve an approximation ratio of l(1 - c/Delta), for some constant c > 0, with constant probability. For the case of hypergraphs where l and Delta are constants, we prove a ratio of l(1 - l-1/8 Delta). The latter is done by analysing the expected size of the hitting set and using concentration inequalities. Moreover, for quasi-regularisable hypergraphs, we achieve an approximation ratio of l(1 - n/8m). We show how and when our results improve over the results of Krivelevich, Halperin and Okun. (C) 2014 Elsevier B.V. All rights reserved.

Document Type:	Article
Additional Information:	Times Cited: 0 0
Keywords:	Approximation algorithms, Probabilistic methods, Randomised rounding, Hitting set, Vertex cover, Greedy algorithms
Research affiliation:	OceanRep > The Future Ocean - Cluster of Excellence OceanRep > The Future Ocean - Cluster of Excellence > FO-R11 Kiel University
Refereed:	Yes
Open Access Journal?:	No
Publisher:	Elsevier
Projects:	Future Ocean
Date Deposited:	30 Mar 2015 12:11
Last Modified:	23 Sep 2019 18:33
URI:	https://oceanrep.geomar.de/id/eprint/27485

Actions (login required)

View Item