# Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints

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

## Key facts

- Cited by 41 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Nov 2013.

## Built on by (most cited first, 30 of 41)

- [DeepCore: A Comprehensive Library for Coreset Selection in Deep Learning](https://mlsanity.com/paper/2204.08499/) (2022)
- [Finding Support Examples for In-Context Learning](https://mlsanity.com/paper/2302.13539/) (2023)
- [Robust Counterfactual Explanations on Graph Neural Networks](https://mlsanity.com/paper/2107.04086/) (2021)
- [Dataset Quantization](https://mlsanity.com/paper/2308.10524/) (2023)
- [Submodularity In Machine Learning and Artificial Intelligence](https://mlsanity.com/paper/2202.00132/) (2022)
- [A Coreset Selection of Coreset Selection Literature: Introduction and Recent Advances](https://mlsanity.com/paper/2505.17799/) (2025)
- [Discrepancy-Based Active Learning for Domain Adaptation](https://mlsanity.com/paper/2103.03757/) (2021)
- [Iterative Forward Tuning Boosts In-Context Learning in Language Models](https://mlsanity.com/paper/2305.13016/) (2023)
- [Sample Efficient Demonstration Selection for In-Context Learning](https://mlsanity.com/paper/2506.08607/) (2025)
- [TrimCaching: Parameter-sharing AI Model Caching in Wireless Edge Networks](https://mlsanity.com/paper/2405.03990/) (2024)
- [Submodlib: A Submodular Optimization Library](https://mlsanity.com/paper/2202.10680/) (2022)
- [Rule-Based Error Detection and Correction to Operationalize Movement Trajectory Classification](https://mlsanity.com/paper/2308.14250/) (2023)
- [CATRO: Channel Pruning via Class-Aware Trace Ratio Optimization](https://mlsanity.com/paper/2110.10921/) (2021)
- [Fair Submodular Cover](https://mlsanity.com/paper/2407.04804/) (2024)
- [Building a Winning Team: Selecting Source Model Ensembles using a Submodular Transferability Estimation Approach](https://mlsanity.com/paper/2309.02429/) (2023)
- [Automatic Combination of Sample Selection Strategies for Few-Shot Learning](https://mlsanity.com/paper/2402.03038/) (2024)
- [Network Support for High-performance Distributed Machine Learning](https://mlsanity.com/paper/2102.03394/) (2021)
- [Fast Feature Selection with Fairness Constraints](https://mlsanity.com/paper/2202.13718/) (2022)
- [On Learning Representations for Tabular Data Distillation](https://mlsanity.com/paper/2501.13905/) (2025)
- [Finding Representative Interpretations on Convolutional Neural Networks](https://mlsanity.com/paper/2108.06384/) (2021)
- [Greedy Modality Selection via Approximate Submodular Maximization](https://mlsanity.com/paper/2210.12562/) (2022)
- [Balancing Utility and Fairness in Submodular Maximization (Technical Report)](https://mlsanity.com/paper/2211.00980/) (2022)
- [Representation Online Matters: Practical End-to-End Diversification in Search and Recommender Systems](https://mlsanity.com/paper/2305.15534/) (2023)
- [Incentivized Truthful Communication for Federated Bandits](https://mlsanity.com/paper/2402.04485/) (2024)
- [Exploring Learning Complexity for Efficient Downstream Dataset Pruning](https://mlsanity.com/paper/2402.05356/) (2024)
- [Unifying Formal Explanations: A Complexity-Theoretic Perspective](https://mlsanity.com/paper/2602.18160/) (2026)
- [Deep Submodular Peripteral Networks](https://mlsanity.com/paper/2403.08199/) (2024)
- [Localized Distributional Robustness in Submodular Multi-Task Subset Selection](https://mlsanity.com/paper/2404.03759/) (2024)
- [RIFF: Inducing Rules for Fraud Detection from Decision Trees](https://mlsanity.com/paper/2408.12989/) (2024)
- [Distributionally Robust Coreset Selection under Covariate Shift](https://mlsanity.com/paper/2501.14253/) (2025)

## Abstract (arXiv)

We investigate two new optimization problems -- minimizing a submodular function subject to a submodular lower bound constraint (submodular cover) and maximizing a submodular function subject to a submodular upper bound constraint (submodular knapsack). We are motivated by a number of real-world applications in machine learning including sensor placement and data subset selection, which require maximizing a certain submodular function (like coverage or diversity) while simultaneously minimizing another (like cooperative cost). These problems are often posed as minimizing the difference between submodular functions [14, 35] which is in the worst case inapproximable. We show, however, that by phrasing these problems as constrained optimization, which is more natural for many applications, we achieve a number of bounded approximation guarantees. We also show that both these problems are closely related and an approximation algorithm solving one can be used to obtain an approximation guarantee for the other. We provide hardness results for both problems thus showing that our approximation factors are tight up to log-factors. Finally, we empirically demonstrate the performance and good scalability properties of our algorithms.