Non-monotone Submodular Maximization in Exponentially Fewer Iterations

Understand

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.