Generalized submodular cover problems and applications

DOI10.1016/S0304-3975(99)00130-9MaRDI QIDQ1589434zbMATH OpenOpenAlexFDO

Authors Judit Bar-Ilan, Guy Kortsarz, David Peleg

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)

Recommendations

• scientific article; zbMATH DE number 1323125
• One for the price of two: a unified approach for approximating covering problems
• Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost
• A threshold of ln n for approximating set cover
• A Tight Analysis of the Greedy Algorithm for Set Cover

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1256748 (Why is no real title available?)
• scientific article; zbMATH DE number 1303535 (Why is no real title available?)
• scientific article; zbMATH DE number 1559542 (Why is no real title available?)
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• scientific article; zbMATH DE number 6472583 (Why is no real title available?)
• A Greedy Heuristic for the Set-Covering Problem
• An analysis of the greedy algorithm for the submodular set covering problem
• Approximation algorithms for combinatorial problems
• Dioïds and semirings: Links to fuzzy sets and other applications
• Heuristics for the fixed cost median problem
• How to Allocate Network Centers
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• On the hardness of approximating minimization problems
• On the ratio of optimal integral and fractional covers
• Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data

Cited in

(24)

• Computing a Minimum-Cost k-Hop Steiner Tree in Tree-Like Metrics
• On fixed cost k-flow problems
• Capacitated domination problem
• Network-design with degree constraints
• Approximating source location and star survivable network problems
• Approximating \(k\)-hop minimum-spanning trees
• An improved approximation algorithm for vertex cover with hard capacities
• An algorithmic framework for solving geometric covering problems -- with applications
• On some network design problems with degree constraints
• On Hop-Constrained Steiner Trees in Tree-Like Metrics
• Approximating the weight of shallow Steiner trees
• The fault-tolerant capacitated \(K\)-center problem
• A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks
• Approximating buy-at-bulk and shallow-light \(k\)-Steiner trees
• Minimum-diameter covering problems
• A note on two source location problems
• The minimum shift design problem
• Algorithms for minimum connected capacitated dominating set problem
• Approximating subdense instances of covering problems
• Distributed approximation of capacitated dominating sets
• Improved approximations for buy-at-bulk and shallow-light \(k\)-Steiner trees and \((k,2)\)-subgraph
• Approximation algorithms for the transportation problem with market choice and related models
• Finding bounded diameter minimum spanning tree in general graphs
• Approximating source location and star survivable network problems

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1589434)