[DMANET] IGAFIT Algorithmic Colloquium - 2pm CEST, April 22: Prophet and Secretary Online Algorithms for Matching in General Graphs by Michal Feldman

Dear all,

we would like to invite you to the IGAFIT Algorithmic Colloquium this
Thursday:

April 22, 2021, 14:00 CEST
Michal Feldman, Tel Aviv University
Title: Prophet and Secretary Online Algorithms for Matching in General
Graphs
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.

We would like to invite you to take part in the event including the
networking session. This new event aims to integrate the European
algorithmic community and keep it connected during the times of the
pandemic. The meeting will be held using the Airmeet platform and to attend
please go to https://www.airmeet.com/e/11852f80-a10d-11eb-bb44-d52cffa4c0b3.
You can find more information about the talk on IGAFIT web page:
http://igafit.mimuw.edu.pl/?page_id=483786.

In order to access the Airmeet platform, you will need to register, so that
others know who you are. Then before and after the talk, you will be
located inside a Social Lounge, where discussion tables are visible. Most
of the tables can have up to 8 chairs, and you can join a table by clicking
the "Take a Seat" button on a table. This way you will be able to talk to
people seated currently at the table. When the session starts you will be
automatically switched to see the stage. You can find more instructions on
how to use Airmeet here:
https://www.airmeet.com/hub/step-by-step-guide-use-airmeet-for-attendees/.

We invite you to take part in the event. Please advertise broadly and bring
your students/postdocs as well.

Organization Committee:
Nikhil Bansal
Artur Czumaj
Andreas Feldmann
Danupon Nanongkai
Adi Rosen
Eva Rotenberg
Piotr Sankowski
Christian Sohler

**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************