Stochastic Matching with Few Queries

on YouTube ↗45m

" summary

Non-adaptive algorithm draws R independent sampled realizations, takes a maximum matching from each, and queries the union; R is poly(1/p) so maximum degree per vertex is O(poly(1/p)). Analysis splits edges into crucial/non-crucial by probability Q_e, builds a fractional matching on sampled realized edges, and uses concentration + blossom arguments to round. Proven guarantees: 0.6568+ approximation for unweighted graphs (later improved to 2/3) and 0.5+ constant for weighted, with main open question whether 1−ε is achievable.

AI-written summary · about

" chapters (12)

1. 0:00Intro
2. 0:38The Setting
3. 2:38Applications - Kidney Exchange
4. 6:19Some Algorithms
5. 7:50Survey of non-adaptive algorithms
6. 11:41Algorithm A
7. 16:30Algorithm B
8. 22:49Analysis Outline
9. 25:22The Non-Crucial Edges Lemma
10. 35:04Implication
11. 37:35Better approximations via better procedures
12. 39:33Conclusion