Title: Robust Submodular Maximization: A Non-Uniform Partitioning Approach,
Abstract: We study the problem of maximizing a monotone submodular function subject to
a cardinality constraint $k$, with the added twist that a number of items
$\tau$ from the returned set may be removed. We focus on the worst-case setting
considered in (Orlin et al., 2016), in which a constant-factor approximation
guarantee was given for $\tau = o(\sqrt{k})$. In this paper, we solve a key
open problem raised therein, presenting a new Partitioned Robust (PRo)
submodular maximization algorithm that achieves the same guarantee for more
general $\tau = o(k)$. Our algorithm constructs partitions consisting of
buckets with exponentially increasing sizes, and applies standard submodular
optimization subroutines on the buckets in order to construct the robust
solution. We numerically demonstrate the performance of PRo in data
summarization and influence maximization, demonstrating gains over both the
greedy algorithm and the algorithm of (Orlin et al., 2016).