# Optimal approximation for submodular and supermodular optimization with bounded curvature

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

## Key facts

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

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

- [Data-Efficient Structured Pruning via Submodular Optimization](https://mlsanity.com/paper/2203.04940/) (2022)
- [Submodular + Concave](https://mlsanity.com/paper/2106.04769/) (2021)
- [Learning Interpretable Decision Rule Sets: A Submodular Optimization Approach](https://mlsanity.com/paper/2206.03718/) (2022)
- [Semantic Caching for Low-Cost LLM Serving: From Offline Learning to Online Adaptation](https://mlsanity.com/paper/2508.07675/) (2025)
- [Multi-Receiver Online Bayesian Persuasion](https://mlsanity.com/paper/2106.06480/) (2021)
- [Using Partial Monotonicity in Submodular Maximization](https://mlsanity.com/paper/2202.03051/) (2022)
- [Adaptive Regularized Submodular Maximization](https://mlsanity.com/paper/2103.00384/) (2021)
- [Fast First-Order Methods for Monotone Strongly DR-Submodular Maximization](https://mlsanity.com/paper/2111.07990/) (2021)
- [Nearly Minimax Optimal Submodular Maximization with Bandit Feedback](https://mlsanity.com/paper/2310.18465/) (2023)
- [Resource-Aware Distributed Submodular Maximization: A Paradigm for Multi-Robot Decision-Making](https://mlsanity.com/paper/2204.07520/) (2022)
- [Bandit Submodular Maximization for Multi-Robot Coordination in Unpredictable and Partially Observable Environments](https://mlsanity.com/paper/2305.12795/) (2023)
- [Online Submodular Coordination with Bounded Tracking Regret: Theory, Algorithm, and Applications to Multi-Robot Coordination](https://mlsanity.com/paper/2209.12429/) (2022)
- [On the Approximation Relationship between Optimizing Ratio of Submodular (RS) and Difference of Submodular (DS) Functions](https://mlsanity.com/paper/2101.01631/) (2021)
- [Difference of Submodular Minimization via DC Programming](https://mlsanity.com/paper/2305.11046/) (2023)
- [On Submodular Contextual Bandits](https://mlsanity.com/paper/2112.02165/) (2021)
- [Achieving Long-term Fairness in Submodular Maximization through Randomization](https://mlsanity.com/paper/2304.04700/) (2023)
- [Beyond Submodularity: A Unified Framework of Randomized Set Selection with Group Fairness Constraints](https://mlsanity.com/paper/2304.06596/) (2023)
- [Communication- and Computation-Efficient Distributed Submodular Optimization in Robot Mesh Networks](https://mlsanity.com/paper/2407.10382/) (2024)
- [Submodular Optimization Beyond Nonnegativity: Adaptive Seed Selection in Incentivized Social Advertising](https://mlsanity.com/paper/2109.15180/) (2021)
- [Online Nonsubmodular Minimization with Delayed Costs: From Full Information to Bandit Feedback](https://mlsanity.com/paper/2205.07217/) (2022)
- [Online SuBmodular + SuPermodular (BP) Maximization with Bandit Feedback](https://mlsanity.com/paper/2207.03091/) (2022)
- [Online Nonsubmodular Optimization with Delayed Feedback in the Bandit Setting](https://mlsanity.com/paper/2508.00523/) (2025)
- [Lazy FSCA for Unsupervised Variable Selection](https://mlsanity.com/paper/2103.02687/) (2021)
- [Supermodular Rank: Set Function Decomposition and Optimization](https://mlsanity.com/paper/2305.14632/) (2023)
- [Performance of ℓ1 Regularization for Sparse Convex Optimization](https://mlsanity.com/paper/2307.07405/) (2023)
- [Performance-Aware Self-Configurable Multi-Agent Networks: A Distributed Submodular Approach for Simultaneous Coordination and Network Design](https://mlsanity.com/paper/2409.01411/) (2024)
- [A Note On Deterministic Submodular Maximization With Bounded Curvature](https://mlsanity.com/paper/2409.02943/) (2024)
- [Distributed Online Submodular Maximization under Communication Delays: A Simultaneous Decision-Making Approach](https://mlsanity.com/paper/2603.27803/) (2026)
- [Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions](https://mlsanity.com/paper/2605.07902/) (2026)

## Abstract (arXiv)

We design new approximation algorithms for the problems of optimizing submodular and supermodular functions subject to a single matroid constraint. Specifically, we consider the case in which we wish to maximize a nondecreasing submodular function or minimize a nonincreasing supermodular function in the setting of bounded total curvature c. In the case of submodular maximization with curvature c, we obtain a (1-c/e)-approximation --- the first improvement over the greedy (1-e-c)/c-approximation of Conforti and Cornuejols from 1984, which holds for a cardinality constraint, as well as recent approaches that hold for an arbitrary matroid constraint. Our approach is based on modifications of the continuous greedy algorithm and non-oblivious local search, and allows us to approximately maximize the sum of a nonnegative, nondecreasing submodular function and a (possibly negative) linear function. We show how to reduce both submodular maximization and supermodular minimization to this general problem when the objective function has bounded total curvature. We prove that the approximation results we obtain are the best possible in the value oracle model, even in the case of a cardinality constraint. We define an extension of the notion of curvature to general monotone set functions and show (1-c)-approximation for maximization and 1/(1-c)-approximation for minimization cases. Finally, we give two concrete applications of our results in the settings of maximum entropy sampling, and the column-subset selection problem.