CS Events

Qualifying Exam

Online Matching with Recourse: Random Edge Arrivals


Download as iCal file

Thursday, July 02, 2020, 02:00pm - 03:30pm



Aditi Dudeja

Location : Remote via Webex


Prof. Aaron Bernstein, Prof. Eric Allender, Prof. Sepehr Assadi, Prof. Jingjin Yu

Event Type: Qualifying Exam

Abstract: The matching problem in the online setting models the following situation: we are given a set of servers in advance, the clients arrive one at a time, and each client has edges to some of the servers. Each client must be matched to some incident server upon arrival (or left unmatched) and the algorithm is not allowed to reverse its decisions. This model is motivated by applications in wireless communication, content delivery, and job scheduling. However due to the no-reversal restriction, we are not able to guarantee an exact maximum matching in this model, only an approximate one. Therefore, it is natural to study a different setting where priority is given to match as many clients as possible, and changes to the matching are allowed but expensive. Formally, the goal is to always maintain a maximum matching while minimizing the number of changes to the matching. This model is called the online matching with recourse. We study the more general model where all the vertices are known in advance, but the edges of the graph are revealed one at a time. In this model, there is a lower bound of \Omega(n^2) known even for the case of simple graphs. So, we study a natural relaxation where the edges arrive in a random order. We show that for some special cases of graphs, random arrival is significantly easier. On the other hand, for general graphs the problem is as hard as in the adversarial setting.


Meeting number: 120 076 7179
Password: exam


Join by video system Dial This email address is being protected from spambots. You need JavaScript enabled to view it.

You can also dial and enter your meeting number.

Join by phone +1-650-429-3300 USA Toll Access code: 120 076 7179