*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
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.
