Explore the intricacies of online matching algorithms in a 22-minute IEEE conference talk that delves into the challenges and approaches for handling general arrivals in bipartite matching scenarios. Learn about key concepts such as prefix hardness, relaxation techniques, and the impossibility of certain outcomes. Gain insights from experts Buddhima Gamlath, Michael Kapralov, Andreas Maggiori, Ola Svensson, and David Wajc as they discuss the complexities of online bipartite matching, its extensions, and the central question driving their research. Discover the hard instances that make this problem particularly challenging and understand the implications for practical applications in computer science and optimization.
Overview
Syllabus
Intro
Online Bipartite Matching
Extensions
The Question
Key Challenge of General Arrivals
The Approach
Prefix Hardness
A Relaxation
(Impossible) Hope
Conclusion
The Hard Instance
Taught by
IEEE FOCS: Foundations of Computer Science
