Interest Group on Algorithmic Foundations of Information Technology
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.
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.