A Distributed Algorithm for Partitioned Robust Submodular Maximization

Abstract

In this paper, we consider the problem of maximizing a monotone submodular function subject to a cardinality constraint, with two added twists - The computation is distributed across a number of machines, and we require the solution to be robust against adversarial removals. We provide two versions of a partitioned robust algorithm for this problem, with the difference amounting to whether or not the centralized machine is informed (only in the final stage of the algorithm) which elements will be removed. In both of these cases, we provide a novel constant-factor approximation guarantee with respect to the optimal algorithm. Finally, we validate our algorithms via numerical experiments on real-world data sets in influence maximization and data summarization.