Randomized approximation for the set multicover problem in hypergraphs

DOI10.1007/S00453-014-9962-9MaRDI QIDQ262245zbMATHOpenAlexFDO

Authors Mourad El Ouali, Peter Munstermann, Anand Srivastav

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

zbMATH Keywords

combinatorial optimizationrandomized algorithmapproximation algorithmshypergraphsset coverset multicover

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

• 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

Cites work

• A Greedy Heuristic for the Set-Covering Problem
• A fast approximation algorithm for the multicovering problem
• A randomised approximation algorithm for the hitting set problem
• An approximation algorithm for the partial vertex cover problem in hypergraphs
• 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 the Vertex Cover Problem in Graphs and Hypergraphs
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• Improved approximation algorithms for maximum graph partitioning problems
• On the ratio of optimal integral and fractional covers
• Probabilistic methods for algorithmic discrete mathematics
• Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks
• Randomized approximation of bounded multicovering problems
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Using homogeneous weights for approximating the partial cover problem
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

Cited in

(9)

• Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks
• Approximation algorithm for the multicovering problem
• Approximation of set multi-cover via hypergraph matching
• A randomised approximation algorithm for the hitting set problem
• Approximating the online set multicover problems via randomized winnowing
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• A randomised approximation algorithm for the hitting set problem
• Approximate Set Covering in Uniform Hypergraphs
• Randomized approximation of bounded multicovering problems

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)