# "Bring Your Own Greedy"+Max: Near-Optimal 1/2-Approximations for Submodular Knapsack

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Oct 2019.

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

- [A Framework for Adapting Offline Algorithms to Solve Combinatorial Multi-Armed Bandit Problems with Bandit Feedback](https://mlsanity.com/paper/2301.13326/) (2023)
- [Active Learning in Bayesian Neural Networks with Balanced Entropy Learning Principle](https://mlsanity.com/paper/2105.14559/) (2021)
- [Federated Combinatorial Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2405.05950/) (2024)
- [Fair Submodular Cover](https://mlsanity.com/paper/2407.04804/) (2024)
- [Linear Query Approximation Algorithms for Non-monotone Submodular Maximization under Knapsack Constraint](https://mlsanity.com/paper/2305.10292/) (2023)
- [Ranking with submodular functions on a budget](https://mlsanity.com/paper/2204.04168/) (2022)
- [Optimal Skill Selection for LLM Agents with Provable Bicriteria Guarantees](https://mlsanity.com/paper/2608.19993/) (2026)
- [Practical Parallel Algorithms for Non-Monotone Submodular Maximization](https://mlsanity.com/paper/2308.10656/) (2023)
- [Optimizing Chance-Constrained Submodular Problems with Variable Uncertainties](https://mlsanity.com/paper/2309.14359/) (2023)
- [Enhanced Deterministic Approximation Algorithm for Non-monotone Submodular Maximization under Knapsack Constraint with Linear Query Complexity](https://mlsanity.com/paper/2405.12252/) (2024)
- [Theoretically Grounded Pruning of Large Ground Sets for Constrained, Discrete Optimization](https://mlsanity.com/paper/2410.17945/) (2024)
- [Bandits with Single-Peaked Preferences and Limited Resources](https://mlsanity.com/paper/2510.09425/) (2025)
- [Data-dependent Evaluations for Budgeted Submodular Maximization](https://mlsanity.com/paper/2607.05759/) (2026)
- [PC-SubMax: Efficient Prompt Compression via Regularized Submodular Maximization](https://mlsanity.com/paper/2609.32474/) (2026)

## Abstract (arXiv)

The problem of selecting a small-size representative summary of a large dataset is a cornerstone of machine learning, optimization and data science. Motivated by applications to recommendation systems and other scenarios with query-limited access to vast amounts of data, we propose a new rigorous algorithmic framework for a standard formulation of this problem as a submodular maximization subject to a linear (knapsack) constraint. Our framework is based on augmenting all partial Greedy solutions with the best additional item. It can be instantiated with negligible overhead in any model of computation, which allows the classic greedy algorithm and its variants to be implemented. We give such instantiations in the offline (Greedy+Max), multi-pass streaming (Sieve+Max) and distributed (Distributed+Max) settings. Our algorithms give (1/2-ε)-approximation with most other key parameters of interest being near-optimal. Our analysis is based on a new set of first-order linear differential inequalities and their robust approximate versions. Experiments on typical datasets (movie recommendations, influence maximization) confirm scalability and high quality of solutions obtained via our framework. Instance-specific approximations are typically in the 0.6-0.7 range and frequently beat even the (1-1/e) ≈ 0.63 worst-case barrier for polynomial-time algorithms.