Randomized approximation for the set multicover problem in hypergraphs
DOI10.1007/S00453-014-9962-9zbMATH Open1336.68293OpenAlexW2075631357MaRDI QIDQ262245FDOQ262245
Peter Munstermann, Anand Srivastav, Mourad El Ouali
Publication date: 29 March 2016
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-014-9962-9
Recommendations
- Approximation algorithm for the multicovering problem
- Approximation of set multi-cover via hypergraph matching
- A randomised approximation algorithm for the partial vertex cover problem in hypergraphs
- Randomized approximation of bounded multicovering problems
- On approximation of the vertex cover problem in hypergraphs
combinatorial optimizationrandomized algorithmapproximation algorithmshypergraphsset coverset multicover
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)
Cites Work
- Approximation algorithms for combinatorial problems
- A Greedy Heuristic for the Set-Covering Problem
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- A fast approximation algorithm for the multicovering problem
- On the ratio of optimal integral and fractional covers
- Probabilistic methods for algorithmic discrete mathematics
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Using homogeneous weights for approximating the partial cover problem
- Approximation algorithms for maximization problems arising in graph partitioning
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
- Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
- Approximate Set Covering in Uniform Hypergraphs
- Approximation algorithms for partial covering problems
- An approximation algorithm for the partial vertex cover problem in hypergraphs
- Randomized approximation of bounded multicovering problems
- Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
- A randomised approximation algorithm for the hitting set problem
- Improved approximation algorithms for maximum graph partitioning problems
- Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks
Cited In (7)
- Randomized approximation of bounded multicovering problems
- Approximating the online set multicover problems via randomized winnowing
- Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks
- Approximation algorithm for the multicovering problem
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Approximate Set Covering in Uniform Hypergraphs
- Approximation of set multi-cover via hypergraph matching
This page was built for publication: Randomized approximation for the set multicover problem in hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q262245)
