Constrained submodular function maximization has been used in subset
selection problems such as selection of most informative sensor locations.
While these models have been quite popular, the solutions Constrained
submodular function maximization has been used in subset selection problems
such as selection of most informative sensor locations. While these models have
been quite popular, the solutions obtained via this approach are unstable to
perturbations in data defining the submodular functions. Robust submodular
maximization has been proposed as a richer model that aims to overcome this
discrepancy as well as increase the modeling scope of submodular optimization.
In this work, we consider robust submodular maximization with structured
combinatorial constraints and give efficient algorithms with provable
guarantees. Our approach is applicable to constraints defined by single or
multiple matroids, knapsack as well as distributionally robust criteria. We
consider both the offline setting where the data defining the problem is known
in advance as well as the online setting where the input data is revealed over
time. For the offline setting, we give a general (nearly) optimal bi-criteria
approximation algorithm that relies on new extensions of classical algorithms
for submodular maximization. For the online version of the problem, we give an
algorithm that returns a bi-criteria solution with sub-linear regret.

本文提出了鲁棒次模函数最大化及其在结构组合约束下的有效算法，旨在提高对次模优化的建模范围，尤其应用于单个或多个基序，背包以及具有分散鲁棒性的标准约束条件，该算法适用于离线和在线设置，并且在线问题的双标准解决方案具有 sub-linear 的遗憾。