Center for Algorithms and Theory of Computation

CS 269S, Fall 2021: Theory Seminar


October 15, 2021, 1:00 – 1:50pm: DBH 1427

Recent Advances in Online Matching: Edge-Weighted

Thorben Tröbst

Abstract: The problem of giving an algorithm for edge-weighted bipartite online matching that beats the trivial greedy algorithm was open for almost 30 years until Zadimoghaddam's recent breakthrough result. It has since been improved two more times by Fahrbach, Huang, Tao, and Zadimoghaddam (FOCS 2020) as well as by Charikar and Blanc (2021). I will give an overview of these new algorithms and of the primary tool used to prove them: the online correlated selection problem.