Fully Online Matching

We introduce a fully online model of maximum cardinality matching in which all vertices arrive online. On the arrival of a vertex, its incident edges to previously-arrived vertices are revealed. Each vertex has a deadline that is after all its neighbors’ arrivals. If a vertex remains unmatched until its deadline, the algorithm must then irrevocably either match it to an unmatched neighbor, or leave it unmatched. The model generalizes the existing one-sided online model and is motivated by applications including ride-sharing platforms, real-estate agency, etc.

We show that the Ranking algorithm by Karp et al. (STOC 1990) is 0.5211-competitive in our fully online model for general graphs. Our analysis brings a novel charging mechanic into the randomized primal-dual technique by Devanur et al. (SODA 2013), allowing a vertex other than the two endpoints of a matched edge to share the gain. To our knowledge, this is the first analysis of Ranking that beats 0.5 on general graphs in an online matching problem, a first step towards solving the open problem by Karp et al. (STOC 1990) about the optimality of Ranking on general graphs. If the graph is bipartite, we show that the competitive ratio of Ranking is exactly the Omega constant, which is approximately 0.5671. Finally, we prove that the fully online model is strictly harder than the previous model as no online algorithm can be 0.6317 < (1-1/e)-competitive in our model even for bipartite graphs.

Speaker Details

Zhiyi is an assistant professor of Computer Science at the University of Hong Kong. He works broadly on theoretical computer science, in particular, on algorithmic game theory, online algorithms, and differential privacy. Before joining HKU, Zhiyi was a postdoc at Stanford University from 2013 to 2014, working with Tim Roughgarden. Before that, he obtained his Ph.D. from the University of Pennsylvania under Sampath Kannan and Aaron Roth in 2013, interned at Microsoft Research Redmond under Nikhil R. Devanur in the summers of 2011 and 2012, and got his bachelor degree from the first “Yao Class” under Andrew Yao at Tsinghua University in 2008.

Series:
Microsoft Research Talks
Date:
Speakers:
Zhiyi Huang
Affiliation:
Computer Science at the University of Hong Kong

Series: Microsoft Research Talks