Simultaenous Sieves: A Deterministic Streaming Algorithm for Non-Monotone Submodular Maximization
This work addresses a core optimization challenge in machine learning and data mining, offering a deterministic streaming solution with improved guarantees for non-monotone submodular maximization, which is incremental over prior randomized methods.
The paper tackles the problem of maximizing a non-monotone submodular function under a cardinality constraint in a single-pass streaming setting, presenting a deterministic algorithm that achieves an approximation ratio of approximately 0.2689 in polynomial time, improving upon the previous best factor of 1/9.
In this work, we present a combinatorial, deterministic single-pass streaming algorithm for the problem of maximizing a submodular function, not necessarily monotone, with respect to a cardinality constraint (SMCC). In the case the function is monotone, our algorithm reduces to the optimal streaming algorithm of Badanidiyuru et al. (2014). In general, our algorithm achieves ratio $α/ (1 + α) - \varepsilon$, for any $\varepsilon > 0$, where $α$ is the ratio of an offline (deterministic) algorithm for SMCC used for post-processing. Thus, if exponential computation time is allowed, our algorithm deterministically achieves nearly the optimal $1/2$ ratio. These results nearly match those of a recently proposed, randomized streaming algorithm that achieves the same ratios in expectation. For a deterministic, single-pass streaming algorithm, our algorithm achieves in polynomial time an improvement of the best approximation factor from $1/9$ of previous literature to $\approx 0.2689$.