A Randomised Approximation Algorithm for the Hitting Set Problem

DOI10.1007/978-3-642-36065-7_11zbMath1379.68349OpenAlexW2177750332MaRDI QIDQ4914439

Helena Fohlin, Anand Srivastav, Mourad El Ouali

Publication date: 12 April 2013

Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-36065-7_11

zbMATH Keywords

approximation algorithmsvertex coverprobabilistic methodsgreedyhitting setrandomised rounding

Mathematics Subject Classification ID

Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Randomized algorithms (68W20)

This page was built for publication: A Randomised Approximation Algorithm for the Hitting Set Problem