Non-monotone Submodular Maximization in Exponentially Fewer Iterations

Abstract

In this paper we consider parallelization for applications whose objective can be expressed as maximizing a non-monotone submodular function under a cardinality constraint. Our main result is an algorithm whose approximation is arbitrarily close to $1/2e$ in $O({\log }^{2}n)$ adaptive rounds, where $n$ is the size of the ground set. This is an exponential speedup in parallel running time over any previously studied algorithm for constrained non-monotone submodular maximization. Beyond its provable guarantees, the algorithm performs well in practice. Specifically, experiments on traffic monitoring and personalized data summarization applications show that the algorithm finds solutions whose values are competitive with state-of-the-art algorithms while running in exponentially fewer parallel iterations.

Cited by in corpus (8)

• Causal Mediation Analysis for Interpreting Neural NLP: The Case of Gender Bias
• Submodular Streaming in All its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity
• The FAST Algorithm for Submodular Maximization
• Parallel Algorithm for Non-Monotone DR-Submodular Maximization
• Adaptivity in Adaptive Submodularity
• Practical and Parallelizable Algorithms for Non-Monotone Submodular Maximization with Size Constraint
• Instance Specific Approximations for Submodular Maximization
• Guarantees of Stochastic Greedy Algorithms for Non-monotone Submodular Maximization with Cardinality Constraint