# Performance guarantees of forward and reverse greedy algorithms for minimizing nonsupermodular nonsubmodular functions on a matroid

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Mar 2021.

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

- [Robust Gaussian Processes via Relevance Pursuit](https://mlsanity.com/paper/2410.24222/) (2024)

## Abstract (arXiv)

This letter studies the problem of minimizing increasing set functions, or equivalently, maximizing decreasing set functions, over the base of a matroid. This setting has received great interest, since it generalizes several applied problems including actuator and sensor placement problems in control theory, multi-robot task allocation problems, video summarization, and many others. We study two greedy heuristics, namely, the forward and the reverse greedy algorithms. We provide two novel performance guarantees for the approximate solutions obtained by these heuristics depending on both the submodularity ratio and the curvature.