Greedy approximations for minimum submodular cover with submodular cost

DOI10.1007/S10589-009-9269-YMaRDI QIDQ2379694zbMATH OpenOpenAlexFDO

Authors Peng-Jun Wan, Du Ding-Zhu, Panos M. Pardalos, Weili Wu

Publication date 19 March 2010

Published in Computational Optimization and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10589-009-9269-y

zbMATH Keywords

greedy approximationsminimum submodular cover

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• Greedy guarantees for minimum submodular cost submodular/non-submodular cover problem
• On minimum submodular cover with submodular cost
• Greedy -approximation algorithm for covering with arbitrary constraints and submodular cost
• Greedy ${\ensuremath{\Delta}}$ -Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost
• On approximation of the submodular set cover problem
• Approximation algorithms for the submodular edge cover problem with submodular penalties
• Minimum non-submodular cover problem with applications
• Approximation algorithms for the minimum power cover problem with submodular/linear penalties
• SOFSEM 2005: Theory and Practice of Computer Science
• Revisiting the approximation bound for stochastic submodular cover

Cites work

• An analysis of the greedy algorithm for the submodular set covering problem
• scientific article; zbMATH DE number 1256748 (Why is no real title available?)
• scientific article; zbMATH DE number 1416629 (Why is no real title available?)
• Network lifetime and power assignment in ad hoc wireless networks

Cited in

(24)

• On non-integer submodular set cover problem
• Greedy -approximation algorithm for covering with arbitrary constraints and submodular cost
• Approximations for node-weighted Steiner tree in unit disk graphs
• Optimal RSUs placement with delay bounded message dissemination in vehicular networks
• A refined analysis of submodular greedy
• Greedy guarantees for minimum submodular cost submodular/non-submodular cover problem
• Minimum hitting set of interval bundles problem: computational complexity and approximability
• A general greedy approximation algorithm for finding minimum positive influence dominating sets in social networks
• Minimum non-submodular cover problem with applications
• PTAS for routing-cost constrained minimum connected dominating set in growth bounded graphs
• Handling least privilege problem and role mining in RBAC
• A cross-monotonic cost-sharing scheme for the concave facility location game
• Algorithm 996
• A Tight Bound for Stochastic Submodular Cover
• On minimum submodular cover with submodular cost
• A bicriteria approximation algorithm for minimum submodular cost partial multi-cover problem
• A unified greedy approximation for several dominating set problems
• A note for approximating the submodular cover problem over integer lattice with low adaptive and query complexities
• Approximation algorithms for the submodular hitting set problem
• Efficient parallel algorithm for minimum cost submodular cover problem with lower adaptive complexity
• On greedy approximation algorithm for the minimum resolving dominating set problem
• Practical algorithm for minimum cost submodular cover problem with performance guarantees
• Approximations for fault-tolerant total and partial positive influence domination
• An approximation algorithm for submodular hitting set problem with linear penalties

This page was built for publication: Greedy approximations for minimum submodular cover with submodular cost

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