# An Efficient Framework for Balancing Submodularity and Cost

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Feb 2020.

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

- [Adaptive Regularized Submodular Maximization](https://mlsanity.com/paper/2103.00384/) (2021)
- [Balancing Utility and Fairness in Submodular Maximization (Technical Report)](https://mlsanity.com/paper/2211.00980/) (2022)
- [Optimal Skill Selection for LLM Agents with Provable Bicriteria Guarantees](https://mlsanity.com/paper/2608.19993/) (2026)
- [Optimal Data Selection: An Online Distributed View](https://mlsanity.com/paper/2201.10547/) (2022)
- [A QUBO Framework for Team Formation](https://mlsanity.com/paper/2503.23209/) (2025)
- [Online Two-Stage Submodular Maximization](https://mlsanity.com/paper/2510.19480/) (2025)
- [Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions](https://mlsanity.com/paper/2605.07902/) (2026)
- [PC-SubMax: Efficient Prompt Compression via Regularized Submodular Maximization](https://mlsanity.com/paper/2609.32474/) (2026)

## Abstract (arXiv)

In the classical selection problem, the input consists of a collection of elements and the goal is to pick a subset of elements from the collection such that some objective function f is maximized. This problem has been studied extensively in the data-mining community and it has multiple applications including influence maximization in social networks, team formation and recommender systems. A particularly popular formulation that captures the needs of many such applications is one where the objective function f is a monotone and non-negative submodular function. In these cases, the corresponding computational problem can be solved using a simple greedy (1-frac1e)-approximation algorithm. In this paper, we consider a generalization of the above formulation where the goal is to optimize a function that maximizes the submodular function f minus a linear cost function c. This formulation appears as a more natural one, particularly when one needs to strike a balance between the value of the objective function and the cost being paid in order to pick the selected elements. We address variants of this problem both in an offline setting, where the collection is known a priori, as well as in online settings, where the elements of the collection arrive in an online fashion. We demonstrate that by using simple variants of the standard greedy algorithm (used for submodular optimization) we can design algorithms that have provable approximation guarantees, are extremely efficient and work very well in practice.