Online Matching with General Arrivals
Offered By: IEEE via YouTube
Course Description
Overview
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.
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
Tags
Related Courses
An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games Against NatureIEEE via YouTube Computation in the Brain Tutorial - Part 2
IEEE via YouTube Computation in the Brain - Part 1
IEEE via YouTube Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model
IEEE via YouTube Cookbook Lower Bounds for Statistical Inference in Distributed and Constrained Settings - Part 1
IEEE via YouTube