Randomized Algorithms for Monotone Submodular Function Maximization on the Integer Lattice
This work addresses optimization challenges in discrete scenarios with repeated item selections, such as resource allocation or recommendation systems, offering an incremental improvement by extending stochastic greedy algorithms to the integer lattice domain.
The paper tackles the problem of maximizing monotone DR-submodular functions on a bounded integer lattice under a cardinality constraint, presenting a randomized algorithm that achieves an O(1 - 1/e - epsilon) approximation guarantee and demonstrating faster performance on synthetic functions compared to existing methods.
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.