# On the Approximation Relationship between Optimizing Ratio of Submodular (RS) and Difference of Submodular (DS) Functions

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 39 references that are in the map.
- First posted on arXiv 5 Jan 2021.

## Builds on (most cited first, 3 of 3)

- [Optimal approximation for submodular and supermodular optimization with bounded curvature](https://mlsanity.com/paper/1311.4728/) (2013)
- [Submodular Maximization Beyond Non-negativity: Guarantees, Fast Algorithms, and Applications](https://mlsanity.com/paper/1904.09354/) (2019)
- [Guess Free Maximization of Submodular and Linear Sums](https://mlsanity.com/paper/1810.03813/) (2018)

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

- [When Combinatorial Thompson Sampling meets Approximation Regret](https://mlsanity.com/paper/2302.11182/) (2023)
- [Difference of Submodular Minimization via DC Programming](https://mlsanity.com/paper/2305.11046/) (2023)
- [Optimal Skill Selection for LLM Agents with Provable Bicriteria Guarantees](https://mlsanity.com/paper/2608.19993/) (2026)

## Abstract (arXiv)

We demonstrate that from an algorithm guaranteeing an approximation factor for the ratio of submodular (RS) optimization problem, we can build another algorithm having a different kind of approximation guarantee -- weaker than the classical one -- for the difference of submodular (DS) optimization problem, and vice versa. We also illustrate the link between these two problems by analyzing a textscGreedy algorithm which approximately maximizes objective functions of the form Psi(f,g), where f,g are two non-negative, monotone, submodular functions and Psi is a quasiconvex 2-variables function, which is non decreasing with respect to the first variable. For the choice Psi(f,g)triangleq f/g, we recover RS, and for the choice Psi(f,g)triangleq f-g, we recover DS. To the best of our knowledge, this greedy approach is new for DS optimization. For RS optimization, it reduces to the standard textscGreedRatio algorithm that has already been analyzed previously. However, our analysis is novel for this case.