Approximation algorithm for the multicovering problem

DOI10.1007/s10878-020-00688-9zbMath1468.90107arXiv2003.06936OpenAlexW3119319396MaRDI QIDQ2025081

Anand Srivastav, Mourad El Ouali, Mohamed Hachimi, Abbass Gorgi

Publication date: 11 May 2021

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2003.06936

zbMATH Keywords

approximation algorithmhypergraphsrandomized roundinginteger linear programs\(\mathbf{k}\)-matchingset cover and set multicover

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• A fast approximation algorithm for the multicovering problem
• Approximation algorithms for combinatorial problems
• On the ratio of optimal integral and fractional covers
• Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Using Homogeneous Weights for Approximating the Partial Cover Problem
• A Greedy Heuristic for the Set-Covering Problem
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
• Approximation algorithms for partial covering problems
• Mathematical Foundations of Computer Science 2005
• An approximation algorithm for the partial vertex cover problem in hypergraphs