DOS Seminar - Alfredo Torrico

Event Details
  • Date/Time:
    • Friday April 20, 2018 - Saturday April 21, 2018
      11:00 am - 11:59 am
  • Location: Groseclose 402
  • Phone:
  • URL:
  • Email:
  • Fee(s):
  • Extras:
No contact information submitted.

Summary Sentence: DOS Seminar - Alfredo Torrico

Full Summary: No summary paragraph submitted.

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.

Additional Information

In Campus Calendar

School of Industrial and Systems Engineering (ISYE)

Invited Audience
Faculty/Staff, Public, Undergraduate students
No categories were selected.
No keywords were submitted.
  • Created By: nhendricks6
  • Workflow Status: Published
  • Created On: Apr 16, 2018 - 10:56am
  • Last Updated: Apr 16, 2018 - 10:56am