# Data-dependent Evaluations for Budgeted Submodular Maximization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 28 references that are in the map.
- First posted on arXiv 7 Jul 2026.

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

- ["Bring Your Own Greedy"+Max: Near-Optimal 1/2-Approximations for Submodular Knapsack](https://mlsanity.com/paper/1910.05646/) (2019)
- [The FAST Algorithm for Submodular Maximization](https://mlsanity.com/paper/1907.06173/) (2019)
- [Leveraging Sparsity for Efficient Submodular Data Summarization](https://mlsanity.com/paper/1703.02690/) (2017)
- [Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint](https://mlsanity.com/paper/2008.05391/) (2020)
- [Information-theoretic Feature Selection via Tensor Decomposition and Submodularity](https://mlsanity.com/paper/2010.16181/) (2020)
- [Instance Specific Approximations for Submodular Maximization](https://mlsanity.com/paper/2102.11911/) (2021)
- [A Refined Analysis of Submodular Greedy](https://mlsanity.com/paper/2102.12879/) (2021)
- [A Primal-Dual Analysis of Monotone Submodular Maximization](https://mlsanity.com/paper/2311.07808/) (2023)

## Abstract (arXiv)

Submodular maximization is an important building block for developing algorithms in many areas such as machine learning and data mining. Due to the NP-hardness of the problem, analysis of submodular maximization algorithms typically provides pessimistic worst-case approximation factors only. It is not easy to evaluate how close a produced solution is to an optimal one for a given problem instance. In this paper, we develop new data-dependent upper bounds for submodular maximization with a knapsack constraint. We theoretically prove that they dominate the optimal solution and empirically demonstrate their advantages in certifying how close to optimal a solution is through experiments with real-world datasets.