Completed
Alternating Path
Class Central Classrooms beta
YouTube videos curated by Class Central.
Classroom Contents
Towards a Better Understanding of Randomized Greedy Matching
Automatically move to the next video in the Classroom when playback concludes
- 1 Intro
- 2 Greedy Matching
- 3 Oblivious Matching Goel and Tripathi 2012
- 4 Understanding of MRG
- 5 Modified Randomized Greedy (MRG)
- 6 Our Algorithm and Results
- 7 Weighted Oblivious Matching
- 8 Perturbed Greedy vs RDO
- 9 Analysis
- 10 Roadmap
- 11 Basic Lower Bound
- 12 Extra Gain: Warm-up Case
- 13 Alternating Path
- 14 Improved Lower Bound: Bipartite
- 15 Bad case in General graph
- 16 A compensation Idea
- 17 Define "Victim"
- 18 v Is Not A Victim?
- 19 Extra gain: General
