Practical Parallel Algorithms for Submodular Maximization Subject to a Knapsack Constraint with Nearly Optimal Adaptivity
Open Access
- 26 June 2023
- journal article
- research article
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the AAAI Conference on Artificial Intelligence
- Vol. 37 (6) , 7261-7269
Abstract
Submodular maximization has wide applications in machine learning and data mining, where massive datasets have brought the great need for designing efficient and parallelizable algorithms. One measure of the parallelizability of a submodular maximization algorithm is its adaptivity complexity, which indicates the number of sequential rounds where a polynomial number of queries to the objective function can be executed in parallel. In this paper, we study the problem of non-monotone submodular maximization subject to a knapsack constraint, and propose the first combinatorial algorithm achieving an (8+epsilon)-approximation under O(log n) adaptive complexity, which is optimal up to a factor of O(loglog n). Moreover, under slightly larger adaptivity, we also propose approximation algorithms with nearly optimal query complexity of O(n), while achieving better approximation ratios. We show that our algorithms can also be applied to the special case of submodular maximization subject to a cardinality constraint, and achieve performance bounds comparable with those of state-of-the-art algorithms. Finally, the effectiveness of our approach is demonstrated by extensive experiments on real-world applications.Keywords
This publication has 9 references indexed in Scilit:
- Practical and Parallelizable Algorithms for Non-Monotone Submodular Maximization with Size ConstraintJournal of Artificial Intelligence Research, 2024
- Constrained Submodular Maximization via a Nonsymmetric TechniqueMathematics of Operations Research, 2019
- Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack ConstraintsMathematics of Operations Research, 2013
- Maximizing Non-monotone Submodular FunctionsSIAM Journal on Computing, 2011
- Maximizing a Monotone Submodular Function Subject to a Matroid ConstraintSIAM Journal on Computing, 2011
- Maximizing Nonmonotone Submodular Functions under Matroid or Knapsack ConstraintsSIAM Journal on Discrete Mathematics, 2010
- A note on maximizing a submodular set function subject to a knapsack constraintOperations Research Letters, 2004
- Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location ProblemsMathematics of Operations Research, 1982
- Distributed Submodular Maximization: Identifying Representative Elements in Massive Data