Unconstrained submodular maximization with constant adaptive complexity

DOI10.1145/3313276.3316327MaRDI QIDQ5212751zbMATH OpenOpenAlexFDO

Authors Lin Chen, Moran Feldman, Amin Karbasi

Publication date 30 January 2020

Published in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1811.06603

zbMATH Keywords

parallel computationsubmodular maximizationlow adaptive complexity

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Parallel algorithms in computer science (68W10)

Abstract: In this paper, we consider the unconstrained submodular maximization problem. We propose the first algorithm for this problem that achieves a tight $(1/2-varepsilon)$-approximation guarantee using $ildeO(varepsilo{n}^{-1})$ adaptive rounds and a linear number of function evaluations. No previously known algorithm for this problem achieves an approximation ratio better than $1/3$ using less than $Omega(n)$ rounds of adaptivity, where $n$ is the size of the ground set. Moreover, our algorithm easily extends to the maximization of a non-negative continuous DR-submodular function subject to a box constraint and achieves a tight $(1/2-varepsilon)$-approximation guarantee for this problem while keeping the same adaptive and query complexities.

Recommendations

• Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time
• An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model
• An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model
• The adaptive complexity of maximizing a submodular function
• Submodular maximization with nearly optimal approximation, adaptivity and query complexity

Cited in

(10)

• Bounds on double-sided myopic algorithms for unconstrained non-monotone submodular maximization
• DR-submodular function maximization with adaptive stepsize
• Practical parallel algorithms for non-monotone submodular maximization
• scientific article; zbMATH DE number 7626767 (Why is no real title available?)
• The adaptive complexity of maximizing a submodular function
• Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time
• An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model
• Submodular maximization subject to a knapsack constraint: combinatorial algorithms with near-optimal adaptive complexity
• A survey on double greedy algorithms for maximizing non-monotone submodular functions
• The one-way communication complexity of submodular maximization with applications to streaming and robustness

This page was built for publication: Unconstrained submodular maximization with constant adaptive complexity

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