# Submodular Maximization under the Intersection of Matroid and Knapsack Constraints

arXiv: https://arxiv.org/abs/2307.09487 · HTML: https://mlsanity.com/paper/2307.09487/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 34 references that are in the map.
- First posted on arXiv 18 Jul 2023.

## Builds on (most cited first, 8 of 8)

- [Regression Under Human Assistance](https://mlsanity.com/paper/1909.02963/) (2019)
- [Efficient Combinatorial Optimization for Word-level Adversarial Textual Attack](https://mlsanity.com/paper/2109.02229/) (2021)
- [Do Less, Get More: Streaming Submodular Maximization with Subsampling](https://mlsanity.com/paper/1802.07098/) (2018)
- [Greed is Good: Near-Optimal Submodular Maximization via Greedy Optimization](https://mlsanity.com/paper/1704.01652/) (2017)
- [Submodular Maximization in Clean Linear Time](https://mlsanity.com/paper/2006.09327/) (2020)
- [Submodular Maximization Through Barrier Functions](https://mlsanity.com/paper/2002.03523/) (2020)
- [Streaming Submodular Maximization under a k-Set System Constraint](https://mlsanity.com/paper/2002.03352/) (2020)
- [How Do You Want Your Greedy: Simultaneous or Repeated?](https://mlsanity.com/paper/2009.13998/) (2020)

## Built on by (most cited first, 2 of 2)

- [Assortment Planning with Sponsored Products](https://mlsanity.com/paper/2402.06158/) (2024)
- [Matroid Algorithms Under Size-Sensitive Independence Oracles](https://mlsanity.com/paper/2605.00201/) (2026)

## Abstract (arXiv)

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.