Breaking Barriers: Combinatorial Algorithms for Non-Monotone Submodular Maximization with Sublinear Adaptivity and 1/e Approximation

With the rapid growth of data in modern applications, parallel algorithms for maximizing nonmonotone submodular functions have gained significant attention. In the parallel computation setting, the state-of-the-art approximation ratio of 1/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/e -ε approximation ratio. This result bridges the gap between continuous and combinatorial approaches for this problem. As a byproduct, we also develop a simpler (1/4 -ε)-approximation algorithm with high probability (≥ 1 -1/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/4 -ε)approximation algorithm particularly efficient in queries.