liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
A randomised approximation algorithm for the hitting set problem
University of Kiel, Germany.
Linköping University, Department of Clinical and Experimental Medicine, Division of Clinical Sciences. Linköping University, Faculty of Health Sciences. Östergötlands Läns Landsting, Center for Health and Developmental Care, Regional Cancer Center South East Sweden.
University of Kiel, Germany.
2014 (English)In: Theoretical Computer Science, ISSN 0304-3975, Vol. 555, 23-34 p.Article in journal (Refereed) Published
Abstract [en]

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 greater than 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.

Place, publisher, year, edition, pages
Elsevier , 2014. Vol. 555, 23-34 p.
Keyword [en]
Approximation algorithms; Probabilistic methods; Randomised rounding; Hitting set; Vertex cover; Greedy algorithms
National Category
Computer and Information Science Mathematics
URN: urn:nbn:se:liu:diva-112302DOI: 10.1016/j.tcs.2014.03.029ISI: 000343627600004OAI: diva2:765671
Available from: 2014-11-24 Created: 2014-11-24 Last updated: 2015-10-02

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Fohlin, Helena
By organisation
Division of Clinical SciencesFaculty of Health SciencesRegional Cancer Center South East Sweden
In the same journal
Theoretical Computer Science
Computer and Information ScienceMathematics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 94 hits
ReferencesLink to record
Permanent link

Direct link