Georgia Tech SCL Georgia Tech SCL Georgia Tech SCL

TITLE: Robust submodular maximization under matroid constraints: offline and online algorithms

ABSTRACT: We consider the robust submodular maximization problem subject to a matroid constraint in the offline as well as online setting. In the offline version we are given a collection of k monotone submodular functions and a matroid on a ground set of size $n$. The goal is to select one independent set that maximizes the minimum of the submodular functions. This problem is known to be NP-hard to approximate to any polynomial factor. We design a  bi-criteria approximation algorithm that returns a set S with (nearly) optimal value and such that it is the union of few independent sets. This result improves on the previous ones known for uniform matroids or the general matroid case when $k$ is constant. Our result also implies similar bi-criteria approximation for the knapsack constraint as well as multiple matroid constraints. We also note that no bi-criteria approximation algorithm is possible for non-monotone submodular functions in contrast to the setting of a single submodular function.
In the online version of the problem, we receive a new collection of functions at each time step and aim to pick an independent set in every stage. We measure the performance of the algorithm in the regret setting where the goal is to give a solution that compares well to picking a single set for all stages. Again, we give a bi-criteria approximation algorithm which has a (nearly) optimal approximation as well as sub-linear regret bounds.