Explore edge-weighted online bipartite matching in this 28-minute IEEE conference talk. Delve into competitive ratio, free disposal, and related works in adversarial order. Examine main results, including deterministic greedy and two-choice greedy algorithms with independent random bits and perfect negative correlation. Learn about online correlated selection (OCS) and three main tools: online primal-dual method, complementary CDF viewpoint, and updating dual variables. Analyze the edge-weighted matching algorithm and factor-revealing linear program. Conclude by discussing open problems in this field of algorithmic research.
Overview
Syllabus
Intro
Edge-weighted online bipartite matching
Competitive ratio
Free disposal
Related works (adversarial order)
Main result
Deterministic greedy
Two-choice greedy with independent random bits
Two-choice greedy with perfect negative correlation
Online correlated selection (OCS)
Three main tools
Online primal-dual method
Complementary CDF viewpoint
Updating the dual variables
Edge-weighted matching algorithm
Analysis roadmap
Factor-revealing linear program
Open problems
Taught by
IEEE FOCS: Foundations of Computer Science
