Breaking Barriers: Combinatorial Algorithms for Non-monotone Submodular Maximization with Sublinear Adaptivity and $1\mathrm{/}e$ Approximation

With the rapid growth of data in modern applications, parallel algorithms for maximizing non-monotone submodular functions have gained significant attention. In the parallel computation setting, the state-of-the-art approximation ratio of $1\mathrm{/}e$ is achieved by a continuous algorithm (Ene & Nguyen, 2020) with adaptivity $O(\log (n))$. In this work, we focus on size constraints and present the first combinatorial algorithm matching this bound – a randomized parallel approach achieving $1\mathrm{/}e-\epsilon$ approximation ratio. This result bridges the gap between continuous and combinatorial approaches for this problem. As a byproduct, we also develop a simpler $(1\mathrm{/}4-\epsilon )$-approximation algorithm with high probability ($\ge 1-1\mathrm{/}n$). Both algorithms achieve $O(\log (n)\log (k))$ adaptivity and $O(n\log (n)\log (k))$ query complexity. Empirical results show our algorithms achieve competitive objective values, with the $(1\mathrm{/}4-\epsilon )$-approximation algorithm particularly efficient in queries.