Non-monotone Submodular Maximization in Exponentially Fewer Iterations

Eric Balkanski, Adam Breuer, Yaron Singer

Neural Information Processing Systems 

In this paper we consider parallelization for applications whose objective can be expressed as maximizing a non-monotone submodular function under a cardinality constraint.