Generalized submodular cover problems and applications

DOI10.1016/S0304-3975(99)00130-9zbMath0952.68063OpenAlexW2087937221MaRDI QIDQ1589434

David Peleg, Judit Bar-Ilan, Guy Kortsarz

Publication date: 12 December 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(99)00130-9

zbMATH Keywords

NP-hard problemsgreedy approximationsubmodular covers

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (22)

Finding bounded diameter minimum spanning tree in general graphs ⋮ On some network design problems with degree constraints ⋮ AN ALGORITHMIC FRAMEWORK FOR SOLVING GEOMETRIC COVERING PROBLEMS — WITH APPLICATIONS ⋮ Distributed approximation of capacitated dominating sets ⋮ A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks ⋮ The fault-tolerant capacitated \(K\)-center problem ⋮ ALGORITHMS FOR MINIMUM CONNECTED CAPACITATED DOMINATING SET PROBLEM ⋮ The minimum shift design problem ⋮ Approximating source location and star survivable network problems ⋮ Capacitated domination problem ⋮ Approximating \(k\)-hop minimum-spanning trees ⋮ Approximation algorithms for the transportation problem with market choice and related models ⋮ Improved approximations for buy-at-bulk and shallow-light \(k\)-Steiner trees and \((k,2)\)-subgraph ⋮ Approximating buy-at-bulk and shallow-light \(k\)-Steiner trees ⋮ A note on two source location problems ⋮ Network-Design with Degree Constraints ⋮ Computing a Minimum-Cost k-Hop Steiner Tree in Tree-Like Metrics ⋮ Approximating Source Location and Star Survivable Network Problems ⋮ Approximating the weight of shallow Steiner trees ⋮ An improved approximation algorithm for vertex cover with hard capacities ⋮ On Hop-Constrained Steiner Trees in Tree-Like Metrics ⋮ On fixed cost \(k\)-flow problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• Dioïds and semirings: Links to fuzzy sets and other applications
• A Greedy Heuristic for the Set-Covering Problem
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Heuristics for the fixed cost median problem
• Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
• How to Allocate Network Centers
• On the hardness of approximating minimization problems

This page was built for publication: Generalized submodular cover problems and applications