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.

翻译：设定子模块目标函数的优化问题有许多真实世界应用。 在可以不止一次选择同一项的离散场景中, 域从 2 元素集成的 2 元素集成为受重度制约的捆绑整形的单调子模块函数最大化问题。 在这项工作中, 我们考虑在 Mirzasoleiman 等人为设定子模块函数而开发的托盘贪婪算法所启发的框架下, 将域的O( 1 - 1/ e - epsilon) 近似概率保证的随机算法普遍化。 我们然后显示, 在合成DR- 子模块函数上, 将我们提议的算法用于显示递减回收属性的整数的值比替代法要快, 包括将目标问题降低到设定的域, 然后应用已知最快的子模块最大化算法。