Approximation of set multi-cover via hypergraph matching
DOI10.1016/j.tcs.2020.09.009zbMath1455.68139OpenAlexW3086317531MaRDI QIDQ2207501
Mourad El Ouali, Abbass Gorgi, Mohamed Hachimi, Anand Srivastav
Publication date: 22 October 2020
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2020.09.009
Analysis of algorithms (68W40) Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Cites Work
- Unnamed Item
- Randomized approximation for the set multicover problem in hypergraphs
- Randomized approximation of bounded multicovering problems
- A randomised approximation algorithm for the hitting set problem
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs
- Approximate Set Covering in Uniform Hypergraphs
- Improved Approximation Guarantees for Packing and Covering Integer Programs
- Reducibility among Combinatorial Problems
- On Approximating (Sparse) Covering Integer Programs
- A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
- Mathematical Foundations of Computer Science 2005
- \(\ell_1\)-sparsity approximation bounds for packing integer programs
- An approximation algorithm for the partial vertex cover problem in hypergraphs
This page was built for publication: Approximation of set multi-cover via hypergraph matching
