Efficient Parallel Algorithms with Linear Queries for Non-Monotone Submodular Maximization

Abstract

In this work, we propose the first constant-approximation algorithms, $\mathsf{LinAst}$ and $\mathsf{LinAtg}$, which simultaneously achieve optimal query complexity $O(n)$ and adaptive complexity $O(\log n)$ for non-monotone submodular maximization under a cardinality constraint $k$ over a ground set of size $n$. Specifically, compared with existing algorithms that attain the best known adaptive complexity of $O(\log n)$, our approach preserves this adaptivity while reducing the query complexity from $O(n \log k)$ to $O(n)$ and improving the approximation ratio from $0.172-\epsilon$ to $0.193-\epsilon$. Our algorithms are built upon $\mathsf{LinAdapt}$, which achieves a constant approximation ratio with $O(\log n)$ adaptive rounds and linear query complexity by requiring only $O(1)$ candidate guesses of the optimal value. We further introduce the $\mathsf{BoostAdapt}$ algorithm, which improves the approximation guarantee to $0.25-\epsilon$ with $O(\log n \log k)$ adaptive complexity and $O(n \log k)$ query complexity, based on a novel staggered greedy threshold framework that alternately constructs two disjoint solution sets over $O(\log k)$ sequential rounds. Extensive experiments on standard benchmark datasets demonstrate that our algorithms consistently outperform state-of-the-art methods in terms of solution quality, query complexity, and running time.