2025/02/10 by Chen, Yixin, Chen, Wenjing, Kuhnle, Alan
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2502.07062
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/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(nlog(n)log(k)) query complexity. Empirical results show our algorithms achieve competitive objective values, with the (1/4-ε)-approximation algorithm particularly efficient in queries.