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.

Presented at:
IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP)

Note: The status of this file is: Anyone

 Record created 2017-11-08, last modified 2020-07-29

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)