A Reduction for Optimizing Lattice Submodular Functions with Diminishing Returns

Abstract

A function $f:{\mathbb{Z}}_{+}^E\to {\mathbb{R}}_{+}$ is DR-submodular if it satisfies $f(\mathbf{x}+{\chi }_i)-f(\mathbf{x})\ge f(\mathbf{y}+{\chi }_i)-f(\mathbf{y})$ for all $\mathbf{x}\le \mathbf{y},i\in E$. Recently, the problem of maximizing a DR-submodular function $f:{\mathbb{Z}}_{+}^E\to {\mathbb{R}}_{+}$ subject to a budget constraint $\Vert \mathbf{x}{\Vert }_1\le B$ as well as additional constraints has received significant attention \cite{SKIK14,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 \emph{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.

Cited by in corpus (10)

• Guaranteed Non-convex Optimization: Submodular Maximization over Continuous Domains
• Gradient Methods for Submodular Maximization
• Fast Maximization of Non-Submodular, Monotonic Functions on the Integer Lattice
• Optimal DR-Submodular Maximization and Applications to Provable Mean Field Inference
• Continuous DR-submodular Maximization: Structure and Algorithms
• Submodular Norms with Applications To Online Facility Location and Stochastic Probing
• Maximizing Non-Monotone DR-Submodular Functions with Cardinality Constraints
• Multiple Knapsack-Constrained Monotone DR-Submodular Maximization on Distributive Lattice --- Continuous Greedy Algorithm on Median Complex ---
• Randomized Algorithms for Monotone Submodular Function Maximization on the Integer Lattice
• Majorisation-minimisation algorithms for minimising the difference between lattice submodular functions