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.