Randomized Online Matching in Regular Graphs
May 17, 2017

In this talk, we will discuss the classic bipartite matching problem in the online setting, first introduced in the seminal work of Karp, Vazirani and Vazirani (STOC '90). Specifically, we consider the problem for the well-studied class of regular graphs. Matching in this class of graphs was studied extensively in the offline setting. In the online setting, an optimal deterministic algorithm, as well as efficient algorithms under stochastic input assumptions were known. In this work, we present a novel randomized algorithm with competitive ratio tending to one on this family of graphs, under adversarial arrival order. Our main result is an algorithm which achieves competitive ratio 1-O(\sqrt{\log d} / \sqrt{d}) in expectation on d-regular graphs, and thus the problem becomes easier for randomized algorithms as d increases (for deterministic algorithms, the optimal competitive ratio is known to decrease as d increases, and tends to 1-1/e). In contrast, we show that all previously-known online algorithms, such as the generally worst-case optimal RANKING algorithm of Karp et al., are restricted to a competitive ratio strictly bounded away from one, even as d grows. Moreover, we show the converge rate of our algorithm's competitive ratio to one is nearly tight, as no algorithm achieves competitive ratio better than 1-O(1 / \sqrt{d}). Finally, we show that our algorithm yields a similar competitive ratio with high probability, as well as guaranteeing each offline vertex a probability of being matched tending to one.

Joint work with Ilan R. Cohen (Hebrew University of Jerusalem).