A randomised approximation algorithm for the hitting set problem

DOI10.1016/j.tcs.2014.03.029zbMath1360.68903OpenAlexW2037738950MaRDI QIDQ744051

Helena Fohlin, Mourad El Ouali, 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

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)

Related Items (6)

An approximation algorithm for submodular hitting set problem with linear penalties ⋮ Parameterized complexity of \(d\)-hitting set with quotas ⋮ Approximation of set multi-cover via hypergraph matching ⋮ Minimal non-odd-transversal hypergraphs and minimal non-odd-bipartite hypergraphs ⋮ Approximation algorithm for the multicovering problem ⋮ Randomized approximation for the set multicover problem in hypergraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Randomized approximation of bounded multicovering problems
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• Improved approximation algorithms for maximum graph partitioning problems
• A fast approximation algorithm for the multicovering problem
• Approximation algorithms for combinatorial problems
• On the ratio of optimal integral and fractional covers
• On approximation of the vertex cover problem in hypergraphs
• Matchings and covers in hypergraphs
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Approximation Algorithms for Maximization Problems Arising in Graph Partitioning
• Algorithmic construction of sets for k -restrictions
• A threshold of ln n for approximating set cover
• New and Improved Bounds for the Minimum Set Cover Problem
• A Greedy Heuristic for the Set-Covering Problem
• A linear-time approximation algorithm for the weighted vertex cover problem
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• On the hardness of approximating minimization problems
• Approximate Set Covering in Uniform Hypergraphs
• Approximation algorithms for partial covering problems

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