# Maximization of Approximately Submodular Functions

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Nov 2024.

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

- [SKILL0: In-Context Agentic Reinforcement Learning for Skill Internalization](https://mlsanity.com/paper/2604.02268/) (2026)
- [Procurement Auctions via Approximately Optimal Submodular Optimization](https://mlsanity.com/paper/2411.13513/) (2024)
- [A Unified Approach to Submodular Maximization Under Noise](https://mlsanity.com/paper/2510.21128/) (2025)
- [Scalable Submodular Policy Optimization via Pruned Submodularity Graph](https://mlsanity.com/paper/2507.13834/) (2025)
- [Joint Semantic Token Selection and Prompt Optimization for Interpretable Prompt Learning](https://mlsanity.com/paper/2605.04425/) (2026)
- [Generating Intervention Hypotheses using Explainable Explanations on Graphs: G2I, a Two-Stage Greedy Framework](https://mlsanity.com/paper/2608.23835/) (2026)

## Abstract (arXiv)

We study the problem of maximizing a function that is approximately submodular under a cardinality constraint. Approximate submodularity implicitly appears in a wide range of applications as in many cases errors in evaluation of a submodular function break submodularity. Say that F is varepsilon-approximately submodular if there exists a submodular function f such that (1-varepsilon)f(S) ≤ F(S)≤ (1+varepsilon)f(S) for all subsets S. We are interested in characterizing the query-complexity of maximizing F subject to a cardinality constraint k as a function of the error level varepsilon>0. We provide both lower and upper bounds: for varepsilon>n-1/2 we show an exponential query-complexity lower bound. In contrast, when varepsilon< 1/k or under a stronger bounded curvature assumption, we give constant approximation algorithms.