Submodular Maximization under the Intersection of Matroid and Knapsack Constraints


  • Yu-Ran Gu Nanjing University
  • Chao Bian Nanjing University
  • Chao Qian Nanjing University



CSO: Constraint Optimization, ML: Optimization


Submodular maximization arises in many applications, and has attracted a lot of research attentions from various areas such as artificial intelligence, finance and operations research. Previous studies mainly consider only one kind of constraint, while many real-world problems often involve several constraints. In this paper, we consider the problem of submodular maximization under the intersection of two commonly used constraints, i.e., k-matroid constraint and m-knapsack constraint, and propose a new algorithm SPROUT by incorporating partial enumeration into the simultaneous greedy framework. We prove that SPROUT can achieve a polynomial-time approximation guarantee better than the state-of-the-art algorithms. Then, we introduce the random enumeration and smooth techniques into SPROUT to improve its efficiency, resulting in the SPROUT++ algorithm, which can keep a similar approximation guarantee. Experiments on the applications of movie recommendation and weighted max-cut demonstrate the superiority of SPROUT++ in practice.




How to Cite

Gu, Y.-R., Bian, C., & Qian, C. (2023). Submodular Maximization under the Intersection of Matroid and Knapsack Constraints. Proceedings of the AAAI Conference on Artificial Intelligence, 37(4), 3959-3967.



AAAI Technical Track on Constraint Satisfaction and Optimization