2026
Efficient Parallel Algorithms with Linear Queries for Non-Monotone Submodular Maximization
IJCAI 2026
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 se