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

Abstract

In this work, we propose the first constant-approximation algorithms, LinAst and 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 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 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.