Randomized approximation for the set multicover problem in hypergraphs

DOI10.1007/s00453-014-9962-9zbMath1336.68293OpenAlexW2075631357MaRDI QIDQ262245

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

zbMATH Keywords

combinatorial optimizationrandomized algorithmhypergraphsapproximation algorithmsset coverset multicover

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 (2)

Approximation of set multi-cover via hypergraph matching ⋮ Approximation algorithm for the multicovering problem

Cites Work

• Unnamed Item
• 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
• A fast approximation algorithm for the multicovering problem
• Approximation algorithms for combinatorial problems
• 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
• Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
• A Greedy Heuristic for the Set-Covering Problem
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Approximate Set Covering in Uniform Hypergraphs
• Approximation algorithms for partial covering problems
• An approximation algorithm for the partial vertex cover problem in hypergraphs

This page was built for publication: Randomized approximation for the set multicover problem in hypergraphs