Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel

For the problem of maximizing a monotone, submodular function with respect to a cardinality constraint k on a ground set of size n, we provide an algorithm that achieves the state-of-the-art in both its empirical performance and its theoretical properties, in terms of adaptive complexity, query complexity, and approximation ratio; that is, it obtains, with high probability, query complexity of O (n) in expectation, adaptivity of O (log(n)), and approximation ratio of nearly 1 -1/e. The main algorithm is assembled from two components which may be of independent interest. The first component of our algorithm, LINEARSEQ, is useful as a preprocessing algorithm to improve the query complexity of many algorithms. Moreover, a variant of LINEARSEQ is shown to have adaptive complexity of O(log(n/k)) which is smaller than that of any previous algorithm in the literature. The second component is a parallelizable thresholding procedure THRESHOLDSEQ for adding elements with gain above a constant threshold. Finally, we demonstrate that our main algorithm empirically outperforms, in terms of runtime, adaptive rounds, total queries, and objective values, the previous state-of-the-art algorithm FAST in a comprehensive evaluation with six submodular objective functions. Version v3. This version fixes two issues in the previous version. Firstly, the prefix selection step in both LINEARSEQ (Alg. 1) and THRESHOLDSEQ (Alg. 4) might result in a significant loss in the objective value. Specifically, when the size of the prefix selected is small (< 1/ε), adding another bad block can ruin the objective value. To address this, we no longer include a bad block if the prefix is small. This is a minor change to the algorithm. Secondly, the analysis of LINEARSEQ incorrectly uses Wald's equation to bound the summation of dependent random variables, specifically in the proof of Inequality 3, as Wald's equation does not apply. In this version, we bound the probabilities of these events in a different way.