On approximation of the submodular set cover problem
From MaRDI portal
Recommendations
- Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties
- Approximation algorithm for stochastic set cover problem
- Primal-dual approximation algorithms for submodular vertex cover problems with linear/submodular penalties
- scientific article; zbMATH DE number 1754596
- Approximation algorithms for partial covering problems
Cites work
- scientific article; zbMATH DE number 1256748 (Why is no real title available?)
- scientific article; zbMATH DE number 1305393 (Why is no real title available?)
- scientific article; zbMATH DE number 910865 (Why is no real title available?)
- A Greedy Heuristic for the Set-Covering Problem
- A unified local ratio approximation of node-deletion problems
- An analysis of the greedy algorithm for the submodular set covering problem
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- Approximation algorithms for combinatorial problems
- Improved performance of the greedy algorithm for partial cover
- On the ratio of optimal integral and fractional covers
- Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
Cited in
(32)- Primal-dual approximation algorithms for submodular vertex cover problems with linear/submodular penalties
- An approximation algorithm for submodular hitting set problem with linear penalties
- Partial multicovering and the d-consecutive ones property
- LATIN 2004: Theoretical Informatics
- On minimum submodular cover with submodular cost
- Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing
- Approximation and Online Algorithms
- Approximating power node-deletion problems
- Approximating power node-deletion problems
- Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties
- Approximation preserving reductions for set covering, vertex covering and independent set hierarchies under differential approximationa
- Approximating bounded degree deletion via matroid matching
- A note on the submodular vertex cover problem with submodular penalties
- A bicriteria approximation algorithm for minimum submodular cost partial multi-cover problem
- Submodular function minimization under a submodular set covering constraint
- Approximating partially bounded degree deletion on directed graphs
- Minimum-cost mixed graph covers with targeted weight constraints
- Approximation algorithm for stochastic set cover problem
- Approximation algorithm for vertex cover with multiple covering constraints
- Submodular Approximation: Sampling-based Algorithms and Lower Bounds
- Approximate Submodularity in Network Design Problems
- Approximation algorithm for vertex cover with multiple covering constraints
- Greedy approximations for minimum submodular cover with submodular cost
- A unified approach to approximating partial covering problems
- Approximating subdense instances of covering problems
- On non-integer submodular set cover problem
- On capacitated set cover problems
- Tight bounds on subexponential time approximation of set cover and related problems
- An approximation algorithm for \(P\)-prize-collecting set cover problem
- A Tight Bound for Stochastic Submodular Cover
- The Exact Subset MultiCover problem
- A note on submodular set cover on matroids
This page was built for publication: On approximation of the submodular set cover problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1969763)
