# A Reduction for Optimizing Lattice Submodular Functions with Diminishing Returns

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Jun 2016.

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

- [Randomized Algorithms for Monotone Submodular Function Maximization on the Integer Lattice](https://mlsanity.com/paper/2111.10175/) (2021)
- [Discrete and Continuous Difference of Submodular Minimization](https://mlsanity.com/paper/2506.07952/) (2025)
- [Fast Approximation Algorithm for Non-Monotone DR-submodular Maximization under Size Constraint](https://mlsanity.com/paper/2511.02254/) (2025)

## Abstract (arXiv)

A function f: mathbbZ_+E rightarrow ℝ_+ is DR-submodular if it satisfies f(bf x + chii) -f (bf x) ≥ f(bf y + chii) - f(bf y) for all bf x≤ bf y, i∈ E. Recently, the problem of maximizing a DR-submodular function f: mathbbZ_+E rightarrow ℝ_+ subject to a budget constraint |bf x|1 ≤ B as well as additional constraints has received significant attention citeSKIK14,SY15,MYK15,SY16. In this note, we give a generic reduction from the DR-submodular setting to the submodular setting. The running time of the reduction and the size of the resulting submodular instance depends only logarithmically on B. Using this reduction, one can translate the results for unconstrained and constrained submodular maximization to the DR-submodular setting for many types of constraints in a unified manner.