liu.seSearch for publications in DiVA
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
A randomised approximation algorithm for the hitting set problem
University of Kiel, Germany.
Linköpings universitet, Institutionen för klinisk och experimentell medicin, Avdelningen för kliniska vetenskaper. Linköpings universitet, Hälsouniversitetet. Östergötlands Läns Landsting, Centrum för hälso- och vårdutveckling, Regionalt cancercentrum.
University of Kiel, Germany.
2014 (engelsk)Inngår i: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 555, s. 23-34Artikkel i tidsskrift (Fagfellevurdert) 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.

sted, utgiver, år, opplag, sider
Elsevier , 2014. Vol. 555, s. 23-34
Emneord [en]
Approximation algorithms; Probabilistic methods; Randomised rounding; Hitting set; Vertex cover; Greedy algorithms
HSV kategori
Identifikatorer
URN: urn:nbn:se:liu:diva-112302DOI: 10.1016/j.tcs.2014.03.029ISI: 000343627600004OAI: oai:DiVA.org:liu-112302DiVA, id: diva2:765671
Tilgjengelig fra: 2014-11-24 Laget: 2014-11-24 Sist oppdatert: 2018-01-11

Open Access i DiVA

Fulltekst mangler i DiVA

Andre lenker

Forlagets fulltekst

Personposter BETA

Fohlin, Helena

Søk i DiVA

Av forfatter/redaktør
Fohlin, Helena
Av organisasjonen
I samme tidsskrift
Theoretical Computer Science

Søk utenfor DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric

doi
urn-nbn
Totalt: 335 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf