On approximation of the submodular set cover problem

DOI10.1016/S0167-6377(99)00045-0zbMath0937.90090OpenAlexW1973935176WikidataQ127315951 ScholiaQ127315951MaRDI QIDQ1969763

Toshihiro Fujito

Publication date: 14 June 2000

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0167-6377(99)00045-0

zbMATH Keywords

optimizationcombinatorial problemdesign of algorithm

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (10)

Approximating Bounded Degree Deletion via Matroid Matching ⋮ Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing ⋮ Approximating power node-deletion problems ⋮ Partial multicovering and the \(d\)-consecutive ones property ⋮ An approximation algorithm for \(P\)-prize-collecting set cover problem ⋮ A unified approach to approximating partial covering problems ⋮ Submodular Function Minimization under a Submodular Set Covering Constraint ⋮ Unnamed Item ⋮ Approximation algorithm for vertex cover with multiple covering constraints ⋮ Approximating Partially Bounded Degree Deletion on Directed Graphs

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

This page was built for publication: On approximation of the submodular set cover problem