Greedy approximations for minimum submodular cover with submodular cost

DOI10.1007/s10589-009-9269-yzbMath1188.90223OpenAlexW2074008775MaRDI QIDQ2379694

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

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

minimum submodular covergreedy approximations

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (15)

An approximation algorithm for submodular hitting set problem with linear penalties ⋮ A cross-monotonic cost-sharing scheme for the concave facility location game ⋮ 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 ⋮ 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 ⋮ Approximations for node-weighted Steiner tree in unit disk graphs ⋮ On minimum submodular cover with submodular cost ⋮ Optimal RSUs placement with delay bounded message dissemination in vehicular networks ⋮ Algorithm 996 ⋮ On the approximability and hardness of the minimum connected dominating set with routing cost constraint ⋮ A Tight Bound for Stochastic Submodular Cover ⋮ Greedy guarantees for minimum submodular cost submodular/non-submodular cover problem ⋮ PTAS for routing-cost constrained minimum connected dominating set in growth bounded graphs ⋮ Handling least privilege problem and role mining in RBAC

Cites Work

• An analysis of the greedy algorithm for the submodular set covering problem
• Algorithms - ESA 2003
• Unnamed Item
• Unnamed Item

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