YoVDO

Fully Online Matching II - Beating Ranking and Water-filling

Offered By: IEEE via YouTube

Tags

IEEE FOCS: Foundations of Computer Science Courses Ranking Algorithms Courses

Course Description

Overview

Explore a 25-minute IEEE conference talk on fully online matching algorithms, focusing on techniques that outperform Ranking and Water-filling. Delve into the economic perspective of these algorithms, learn about Balanced Ranking, and understand the necessity of lookahead water levels. Discover the concept of Eager Water-filling and gain insights into potential future developments in this field. The presentation covers key works by Huang et al. and Karp et al., providing a comprehensive overview of the topic.

Syllabus

Intro
Fully Online Matching Huang et al. JACM 2020
Ranking Karp et al., STOC 1990
Summary
Our Results
Economic view of Ranking & Water-filling
Balanced Ranking
Why we need lookahead water level?
Eager Water-filling
Future Work


Taught by

IEEE FOCS: Foundations of Computer Science

Tags

Related Courses

An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games Against Nature
IEEE 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