Submodular Maximization under k -System Constraints in Parallel: A Trifecta of Approximation, Adaptivity, and Query Complexity
Open Access
- 20 April 2026
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 164-175
Abstract
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.Keywords
Funding Information
- National Natural Science Foundation of China (62502333)
- Basic research program of Jiangsu (BK20250786)
- National Natural Science Foundation of China (62332013)
This publication has 34 references indexed in Scilit:
- Coresets remembered and items forgotten: submodular maximization with deletions2022
- Generalized Submodular Information Measures: Theoretical Properties, Examples, Optimization Algorithms, and ApplicationsIEEE Transactions on Information Theory, 2021
- Guess Free Maximization of Submodular and Linear SumsAlgorithmica, 2020
- Submodular subset selection for large-scale speech training data2014
- Ontology-enriched multi-document summarization in disaster management using submodular functionInformation Sciences, 2013
- Profit Maximization over Social Networks2012
- Multi-document summarization via submodularityApplied Intelligence, 2012
- Constrained Non-monotone Submodular Maximization: Offline and Secretary Algorithms2010
- Greedy in Approximation Algorithms2006
- An analysis of approximations for maximizing submodular set functions—II1978