Submodular Maximization under k-System Constraints in Parallel: A Trifecta of Approximation, Adaptivity, and Query Complexity

Submodular optimization serves as a foundational framework for numerous data mining tasks requiring the extraction of representative subsets from large-scale datasets under combinatorial constraints. In this paper, we study the fundamental problem of maximizing a general submodular function (not necessarily monotone) under a general k-system constraint, and propose a novel parallel algorithm. For this problem, our algorithm is the first to simultaneously achieve nearly best-known guarantees across three key metrics: an approximation ratio of (1-ε)3 (√k+1)-2 , an adaptive complexity of O (√k log2 n), and a query complexity of O (√knlog n), which effectively mitigates the trade-offs in prior work. Moreover, we generalize our approach to solve regularized submodular maximization problems while maintaining the same complexities. To the best of our knowledge, the resulting algorithm is the first parallel algorithm with a provable approximation ratio for this class of problems. We validate our theoretical contributions through extensive experiments on real-world applications, including maximum coverage on networks and movie recommendations. The empirical results strongly show the superiority of our proposed algorithms in terms of objective value, adaptivity, and query efficiency.