A Reduction for Optimizing Lattice Submodular Functions with Diminishing Returns

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.