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

Source: [Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel](<https://www.sota2.com/research/paper/68fa74881e209131cea62494>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2026-01-04T05:12:50.008Z

Authors: Yixin Chen, Tonmoy Dey, Alan Kuhnle

Published: 2021-11-15T17:10:40.000Z

## Abstract

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.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [Submodular Maximization on TrafficMonitor](<https://www.sota2.com/research/sota/submodular-maximization-on-trafficmonitor.md>): Submodular Maximization; TrafficMonitor; Runtime (s): 0.21.

- [Submodular Maximization on InfluenceMax](<https://www.sota2.com/research/sota/submodular-maximization-on-influencemax.md>): Submodular Maximization; InfluenceMax; Runtime (s): 2.3.

- [Submodular Maximization on TwitterSumm](<https://www.sota2.com/research/sota/submodular-maximization-on-twittersumm.md>): Submodular Maximization; TwitterSumm; Runtime (s): 3.5.

- [Submodular Maximization on Revenue Max](<https://www.sota2.com/research/sota/submodular-maximization-on-revenue-max.md>): Submodular Maximization; Revenue Max; Runtime (s): 54.

- [Submodular Maximization on MaxCover BA](<https://www.sota2.com/research/sota/submodular-maximization-on-maxcover-ba.md>): Submodular Maximization; MaxCover BA; Runtime (s): 76.

- [Submodular Maximization on ImageSumm](<https://www.sota2.com/research/sota/submodular-maximization-on-imagesumm.md>): Submodular Maximization; ImageSumm; Runtime (s): 81.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2111.07917>)

[PDF](<https://arxiv.org/pdf/2111.07917.pdf>)

[Implementation](<https://gitlab.com/deytonmoy000/submodular-bestofbothworlds>)
