# Randomized Algorithms for Monotone Submodular Function Maximization on the Integer Lattice

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 29 references that are in the map.
- First posted on arXiv 19 Nov 2021.

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

- [Lazier Than Lazy Greedy](https://mlsanity.com/paper/1409.7938/) (2014)
- [ABCD-Strategy: Budgeted Experimental Design for Targeted Causal Structure Discovery](https://mlsanity.com/paper/1902.10347/) (2019)
- [Submodular Functions: from Discrete to Continous Domains](https://mlsanity.com/paper/1511.00394/) (2015)
- [Submodularity in Action: From Machine Learning to Signal Processing Applications](https://mlsanity.com/paper/2006.09905/) (2020)
- [Maximizing Monotone Submodular Functions over the Integer Lattice](https://mlsanity.com/paper/1503.01218/) (2015)
- [From Sets to Multisets: Provable Variational Inference for Probabilistic Integer Submodular Models](https://mlsanity.com/paper/2006.01293/) (2020)
- [A Reduction for Optimizing Lattice Submodular Functions with Diminishing Returns](https://mlsanity.com/paper/1606.08362/) (2016)

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

- [Fast Approximation Algorithm for Non-Monotone DR-submodular Maximization under Size Constraint](https://mlsanity.com/paper/2511.02254/) (2025)

## Abstract (arXiv)

Optimization problems with set submodular objective functions have many real-world applications. In discrete scenarios, where the same item can be selected more than once, the domain is generalized from a 2-element set to a bounded integer lattice. In this work, we consider the problem of maximizing a monotone submodular function on the bounded integer lattice subject to a cardinality constraint. In particular, we focus on maximizing DR-submodular functions, i.e., functions defined on the integer lattice that exhibit the diminishing returns property. Given any epsilon > 0, we present a randomized algorithm with probabilistic guarantees of O(1 - 1/e - epsilon) approximation, using a framework inspired by a Stochastic Greedy algorithm developed for set submodular functions by Mirzasoleiman et al. We then show that, on synthetic DR-submodular functions, applying our proposed algorithm on the integer lattice is faster than the alternatives, including reducing a target problem to the set domain and then applying the fastest known set submodular maximization algorithm.