Submodular Maximization under the Intersection of Matroid and Knapsack Constraints
This addresses a key limitation in optimization for AI and operations research by handling multiple constraints, though it is incremental as it builds on existing greedy frameworks.
The paper tackles submodular maximization under combined matroid and knapsack constraints, proposing the SPROUT and SPROUT++ algorithms that achieve better polynomial-time approximation guarantees than state-of-the-art methods, with experiments showing practical superiority in movie recommendation and weighted max-cut applications.
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.