Upcoming IGAFIT Colloquia

The IGAFIT Algorithmic Colloquia are organized biweekly on Thursdays at 14:00 CEST. After the talk we will have an online networking/discussion session for approximately 1 hour. Both of these events will be run through the Airmeet platform.

Follow us also on twitter and facebook.

To subscribe to the ICAFIT Algorithmic Colloquium mailing list with announcements send an email to igafit-colloquium-request@mimuw.edu.pl with subject SUBSCRIBE.

The schedule of IGAFIT Algorithmic Colloquia: (see also our schedule of past Colloquia)


IGAFIT Algorithmic Colloquium #12
April 22, 2021
Link: TBA
Prophet and Secretary Online Algorithms for Matching in General Graphs
Michal Feldman, Tel Aviv University
Abstract: A common tension in market scenarios is choosing the right timing to commit to a decision. This tension is captured by the mathematical literature of optimal stopping theory, within two models that have become to be known as the secretary problem and the prophet inequality. In these models, a sequence of originally-unknown values arrive one by one. Upon arrival, the online algorithm observes the value and should decide whether or not to accept it. In secretary settings, the value sequence is arbitrary, but the values arrive in a uniformly random order. In prophet settings, every value is drawn from a known probability distribution, but the arrival order is arbitrary.
In this talk I will review the basic settings of secretary and prophet, as well as previous extensions to matching in bipartite graphs with 1-sided vertex arrival. I will then present our recent work, which studies online algorithms (in both secretary and prophet settings) for matching in general graphs. We provide tight competitive ratios for both secretary and prophet matching scenarios under vertex arrival. Under edge arrival, we provide competitive ratios that improve upon the state of the art.
Based on joint work with Tomer Ezra, Nick Gravin and Zhihao Tang.

IGAFIT Algorithmic Colloquium #13
May 6, 2021
Link: TBA
Title:
Adam Smith, Boston University
Abstract:

IGAFIT Algorithmic Colloquium #14
May 20, 2021
Link: TBA
Title:
Sergei Vassilvitskii, Google Research New York
Abstract:

IGAFIT Algorithmic Colloquium #15
June 10, 2021
Link: TBA
Title:
Virginia Vassilevska Williams, MIT
Abstract:

IGAFIT Algorithmic Colloquium #16
June 17, 2021
Link: TBA
Polyhedral Techniques in Combinatorial Optimization
Ola Svensson, EPFL
Abstract:

IGAFIT Algorithmic Colloquium #17
July 1, 2021
Link: TBA
Title:
Ronitt Rubinfeld, MIT
Abstract:

Past IGAFIT Colloquium talks.


Follow us also on twitter and facebook.

To subscribe to the ICAFIT Algorithmic Colloquium mailing list with announcements send an email to igafit-colloquium-request@mimuw.edu.pl with subject SUBSCRIBE.