# Weakly Submodular Maximization Beyond Cardinality Constraints: Does Randomization Help Greedy?

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jul 2017.

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

- [Using Partial Monotonicity in Submodular Maximization](https://mlsanity.com/paper/2202.03051/) (2022)
- [Submodular Minimax Optimization: Finding Effective Sets](https://mlsanity.com/paper/2305.16903/) (2023)
- [Add-One-In: Incremental Sample Selection for Large Language Models via a Choice-Based Greedy Paradigm](https://mlsanity.com/paper/2503.02359/) (2025)
- [Submodular Framework for Structured-Sparse Optimal Transport](https://mlsanity.com/paper/2406.04914/) (2024)
- [G"odel Test: Can Large Language Models Solve Easy Conjectures?](https://mlsanity.com/paper/2509.18383/) (2025)
- [Fast Feature Selection with Fairness Constraints](https://mlsanity.com/paper/2202.13718/) (2022)
- [AdvCat: Domain-Agnostic Robustness Assessment for Cybersecurity-Critical Applications with Categorical Inputs](https://mlsanity.com/paper/2212.13989/) (2022)
- [Online Nonsubmodular Minimization with Delayed Costs: From Full Information to Bandit Feedback](https://mlsanity.com/paper/2205.07217/) (2022)
- [Scalable Projection-Free Optimization](https://mlsanity.com/paper/2105.03527/) (2021)
- [Supermodular Rank: Set Function Decomposition and Optimization](https://mlsanity.com/paper/2305.14632/) (2023)
- [Neural Autoregressive Flows for Markov Boundary Learning](https://mlsanity.com/paper/2603.20791/) (2026)
- [Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions](https://mlsanity.com/paper/2605.07902/) (2026)
- [Probabilistic Multi-Source Data Selection via Learnable Categorical Priors: Variance Reduction and Guaranteed Derandomization](https://mlsanity.com/paper/2610.14942/) (2026)

## Abstract (arXiv)

Submodular functions are a broad class of set functions, which naturally arise in diverse areas. Many algorithms have been suggested for the maximization of these functions. Unfortunately, once the function deviates from submodularity, the known algorithms may perform arbitrarily poorly. Amending this issue, by obtaining approximation results for set functions generalizing submodular functions, has been the focus of recent works. One such class, known as weakly submodular functions, has received a lot of attention. A key result proved by Das and Kempe (2011) showed that the approximation ratio of the greedy algorithm for weakly submodular maximization subject to a cardinality constraint degrades smoothly with the distance from submodularity. However, no results have been obtained for maximization subject to constraints beyond cardinality. In particular, it is not known whether the greedy algorithm achieves any non-trivial approximation ratio for such constraints. In this paper, we prove that a randomized version of the greedy algorithm (previously used by Buchbinder et al. (2014) for a different problem) achieves an approximation ratio of (1 + 1/γ)-2 for the maximization of a weakly submodular function subject to a general matroid constraint, where γ is a parameter measuring the distance of the function from submodularity. Moreover, we also experimentally compare the performance of this version of the greedy algorithm on real world problems against natural benchmarks, and show that the algorithm we study performs well also in practice. To the best of our knowledge, this is the first algorithm with a non-trivial approximation guarantee for maximizing a weakly submodular function subject to a constraint other than the simple cardinality constraint. In particular, it is the first algorithm with such a guarantee for the important and broad class of matroid constraints.