Deletion-Robust Submodular Maximization Under the Cardinality Constraint over the Integer Lattice

Submodular optimization is a classical problem of combinatorial optimization. The objective functions of many combinatorial optimization problems are submodular functions and they also have significant applications in real life. Since some practical problems such as budget allocations that are hard to be modeled over set functions, submodular functions over the integer lattice have been widely and intensively studied subject to various classical constraints for decades. In this paper we study the robustness of maximizing a monotone diminishing return submodular function over the integer lattice under the cardinality constraint. We propose a robustness model over the integer lattice and design algorithms under this specific model by utilizing stochastic strategy combining with binary search approach. The algorithms we designed in centralized settings can achieve a \((1/2-\delta )\) -approximation and maintain robustness against deleting any d elements adversarially. While in streaming settings the algorithms we designed can still achieve the same approximation and be robust against deleting any d elements adversarially as well.