Non-monotone Submodular Maximization In Exponentially Fewer Iterations

Authors:
Eric Balkanski Harvard University
Adam Breuer Harvard University
Yaron Singer Harvard University

Introduction:

In this paper the authors consider parallelization for applications whose objective can beexpressed as maximizing a non-monotone submodular function under a cardinality constraint.

Abstract:

In this paper we consider parallelization for applications whose objective can beexpressed as maximizing a non-monotone submodular function under a cardinality constraint. Our main result is an algorithm whose approximation is arbitrarily closeto 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.

You may want to know: