A randomised approximation algorithm for the hitting set problem

DOI10.1016/J.TCS.2014.03.029MaRDI QIDQ744051zbMATH OpenOpenAlexFDO

Authors Mourad El Ouali, Helena Fohlin, Anand Srivastav

Publication date 6 October 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2014.03.029

zbMATH Keywords

approximation algorithmsgreedy algorithmsvertex coverprobabilistic methodshitting setrandomised rounding

Mathematics Subject Classification ID

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

Recommendations

• A randomised approximation algorithm for the hitting set problem
• A randomised approximation algorithm for the partial vertex cover problem in hypergraphs
• Randomized approximation for the set multicover problem in hypergraphs
• An approximation algorithm for the partial vertex cover problem in hypergraphs
• Approximating vertex cover in dense hypergraphs

Cites work

• scientific article; zbMATH DE number 3889282 (Why is no real title available?)
• scientific article; zbMATH DE number 43754 (Why is no real title available?)
• scientific article; zbMATH DE number 1246230 (Why is no real title available?)
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• scientific article; zbMATH DE number 1445320 (Why is no real title available?)
• A Greedy Heuristic for the Set-Covering Problem
• A fast approximation algorithm for the multicovering problem
• A linear-time approximation algorithm for the weighted vertex cover problem
• A threshold of ln n for approximating set cover
• Algorithmic construction of sets for k -restrictions
• Approximate Set Covering in Uniform Hypergraphs
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Approximation algorithms for combinatorial problems
• Approximation algorithms for maximization problems arising in graph partitioning
• Approximation algorithms for partial covering problems
• Improved approximation algorithms for MAX k-cut and MAX BISECTION
• Improved approximation algorithms for maximum graph partitioning problems
• Matchings and covers in hypergraphs
• New and improved bounds for the minimum set cover problem
• On approximation of the vertex cover problem in hypergraphs
• On the hardness of approximating minimization problems
• On the ratio of optimal integral and fractional covers
• Randomized approximation of bounded multicovering problems
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

Cited in

(13)

• Randomized approximation for the set multicover problem in hypergraphs
• Minimal non-odd-transversal hypergraphs and minimal non-odd-bipartite hypergraphs
• An approximation algorithm for submodular hitting set problem with linear penalties
• Parameterized complexity of d-hitting set with quotas
• An improved algorithm for the red-blue hitting set problem with the consecutive ones property
• Parameterized algorithms for \(d\)-hitting set: the weighted case
• A randomised approximation algorithm for the hitting set problem
• Sharp concentration of hitting size for random set systems
• Approximation algorithm for the multicovering problem
• Algorithms for implicit hitting set problems
• A randomised approximation algorithm for the partial vertex cover problem in hypergraphs
• Hitting sets online and vertex ranking
• Approximation of set multi-cover via hypergraph matching

This page was built for publication: A randomised approximation algorithm for the hitting set problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q744051)