- This event has passed.
CIS Seminar: “Edge-Weighted Online Bipartite Matching”
November 14, 2023 at 3:30 PM - 4:30 PM
Online bipartite matching is one of the most fundamental problems in the online algorithms literature. Karp, Vazirani, and Vazirani (STOC 1990) gave an elegant algorithm for unweighted bipartite matching that achieves an optimal competitive ratio 1-1/e. Aggarwal et al. (SODA 2011) later generalized their algorithm and analysis to the vertex-weighted case. Little is known, however, about the most general edge-weighted problem aside from the trivial 1/2-competitive greedy algorithm. In this talk, we present the first online algorithm that breaks the long-standing 1/2 barrier and achieves a competitive ratio of at least 0.5086.
The main ingredient in our online matching algorithm is a novel subroutine called online correlated selection (OCS), which takes a sequence of pairs of vertices as input and selects one vertex from each pair. Instead of using a fresh random bit to choose a vertex from each pair, the OCS negatively correlates decisions across different pairs and provides a quantitative measure of the level of correlation. The OCS technique is of independent interest and has already found further applications in other online optimization problems.
Zhiyi Huang
Associate Professor, Computer Science Dept., University of Hong Kong
Zhiyi Huang is an associate professor of Computer Science at the University of Hong Kong. He works broadly on Theoretical Computer Science. Before joining HKU, Zhiyi was a postdoc at Stanford University from 2013 to 2014, working with Tim Roughgarden. He obtained my Ph.D. from the University of Pennsylvania under Sampath Kannan and Aaron Roth in 2013. During grad school, I interned at Microsoft Research Redmond under Nikhil R. Devanur in the summers of 2011 and 2012. Before that, Zhiyi got a bachelor’s degree from the first “Yao Class” under Andrew Yao at Tsinghua University in 2008. Zhiyi was the recipient of the Best Paper Awards of FOCS 2020 and SPAA 2015, an Excellent Young Scientists Fund (HK & Macau) by NSFC, an Early Career Award by RGC Hong Kong, a Morris and Dorothy Rubinoff Dissertation Award, and a Simons Graduate Fellowship in Theoretical Computer Science.