A note for approximating the submodular cover problem over integer lattice with low adaptive and query complexities

DOI10.1016/j.ipl.2023.106393OpenAlexW4360604008MaRDI QIDQ6161454

Canh V. Pham, Unnamed Author

Publication date: 5 June 2023

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2023.106393

zbMATH Keywords

approximation algorithmsinteger latticesubmodular coveradaptive complexity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Maximizing monotone submodular functions over the integer lattice
• An analysis of the greedy algorithm for the submodular set covering problem
• Minimum budget for misinformation blocking in online social networks
• Greedy approximations for minimum submodular cover with submodular cost
• A threshold of ln n for approximating set cover
• An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model
• Submodular maximization with matroid and packing constraints in parallel
• The adaptive complexity of maximizing a submodular function
• Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity
• Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time
• An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
• Fast algorithms for maximizing submodular functions

This page was built for publication: A note for approximating the submodular cover problem over integer lattice with low adaptive and query complexities