International Joint Conference On Theoretical Computer Science – Frontier of Algorithmic Wisdom

August 15-19, 2022, City University of Hong Kong, Hong Kong

 

Invited Speakers

Track G


Recent progress in online matching

Zhiyi Huang

University of Hong Kong

Abstract:
Originated from the seminal work by Karp, Vazirani, and Vazirani (1990), online matching has been established as one of the most fundamental topics in the literature of online algorithms. This talk presents the basics of online matching, and surveys the recent progress in two directions:
1. Open problems about online advertising: AdWords and Display Ads are generalizations of the online bipartite matching problem by Karp et al. These problems capture online advertising which generates tens of billions of US dollars annually. This year, we introduce a new technique called online correlated selection, and design the first online algorithms for the general cases of AdWords and Display Ads outperforming greedy, which has remained the state of the art for more than 10 years, despite many attempts to find better alternatives.
2. General arrival models: Traditional online matching models consider bipartite graphs and assume knowing one side of the bipartite graph upfront. The matching problems in many modern scenarios, however, do not fit into the traditional models. In the problem of matching rid of matching ride-sharing requests, for instance, the graph is not bipartite in general, and all vertices arrive online. There has been much progress in the past three years on online matching models beyond the traditional ones, including the fully online model, the general vertex arrival model, and the edge arrival model.

Bio:
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 his Ph.D. from the University of Pennsylvania under Sampath Kannan and Aaron Roth in 2013. During grad school, Zhiyi interned at Microsoft Research Redmond under Nikhil R. Devanur in the summers of 2011 and 2012. Before that he got a bachelor 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.