Theory Seminar: Online Matching with General Arrivals

Online Matching with General Arrivals

Abstract: The online matching problem was introduced by Karp, Vazirani and Vazirani nearly three decades ago. In that seminal work, they studied this problem in bipartite graphs with vertices arriving only on one side, and presented optimal deterministic and randomized algorithms for this setting. In comparison, more general arrival models, such as edge arrivals and general vertex arrivals, have proven more challenging, and positive results are known only for various relaxations of the problem. In particular, even the basic question of whether randomization allows one to beat the trivially-optimal deterministic competitive ratio of 1/2 for either of these models was open. In this paper, we resolve this question for both these natural arrival models, and show the following.

1. For edge arrivals, randomization does not help -- no randomized algorithm is better than 1/2 competitive. 

2. For general vertex arrivals, randomization helps -- there exists a randomized (1/2+ Ω(1))-competitive online matching algorithm.

Bio: David Wajc is a final-year PhD candidate at Carnegie Mellon University’s Computer Science Theory Group. He is broadly interested in algorithms under uncertainty (online, dynamic, streaming and distributed algorithms), with a focus on matching theory under uncertainty. Prior to coming to CMU, he was a Research Engineer at Yahoo! Labs, and before that he completed his MSc and BSc (summa cum laude) at the Technion — Israel Institute of Technology. David has gone on multiple long-term academic visits over the years, including research internships at Google and IBM, a semester-long visit at EPFL and three extended visits to the Simons Institute for the Theory of Computing at Berkeley.

Based on joint work with Buddhima Gamlath, Michael Kapralov, Andreas Maggiori and Ola Svensson at EPFL, in FOCS 2019. Full version can be found here.