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

low adaptive complexityparallel computationsubmodular maximization

Mathematics Subject Classification ID

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

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

(14)

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

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)