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

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

 

Invited Speakers

Young PhD Forum


The Power of Multiple Choices in Online Stochastic Matching

Xinkai Shu

University of Hong Kong

Abstract:
Online stochastic matching is first proposed by Feldman, Mehta, Mirrokni, and Muthukrishnan (FOCS 2009), motivated by advertising in the internet. Previous works on this problem mainly consider two choices of offline neighbors for each online vertex because of the technical challenge in analyzing multiple choices. In this talk we will present a recent result in STOC ’22 that introduces two approaches for designing and analyzing algorithms that use multiple choices: 1. Global characterization of the progress of matching through a differential inequality, instead of studying individual vertices. 2. Application of online correlated selection (OCS) technique in the stochastic setting.

Bio:
Xinkai Shu is a third-year PhD student at The University of Hong Kong, advised by Prof. Zhiyi Huang. He obtained his bachelor’s degree from Yao class, Tsinghua University. His main research interests are online algorithms and dynamic algorithms.