Online Matching with Recourse: Random Edge Arrivals
Thursday, July 02, 2020, 02:00pm - 03:30pm
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.