On approximation of the submodular set cover problem
From MaRDI portal
Publication:1969763
DOI10.1016/S0167-6377(99)00045-0zbMath0937.90090MaRDI QIDQ1969763
Publication date: 14 June 2000
Published in: Operations Research Letters (Search for Journal in Brave)
90C27: Combinatorial optimization
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved performance of the greedy algorithm for partial cover
- Approximation algorithms for combinatorial problems
- On the ratio of optimal integral and fractional covers
- An analysis of the greedy algorithm for the submodular set covering 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
- A unified local ratio approximation of node-deletion problems