Edge-Weighted Online Bipartite Matching

Edge-Weighted Online Bipartite Matching

IEEE FOCS: Foundations of Computer Science via YouTube Direct link

Edge-weighted online bipartite matching

2 of 18

2 of 18

Edge-weighted online bipartite matching

Class Central Classrooms beta

YouTube videos curated by Class Central.

Classroom Contents

Edge-Weighted Online Bipartite Matching

Automatically move to the next video in the Classroom when playback concludes

  1. 1 Intro
  2. 2 Edge-weighted online bipartite matching
  3. 3 Competitive ratio
  4. 4 Free disposal
  5. 5 Related works (adversarial order)
  6. 6 Main result
  7. 7 Deterministic greedy
  8. 8 Two-choice greedy with independent random bits
  9. 9 Two-choice greedy with perfect negative correlation
  10. 10 Online correlated selection (OCS)
  11. 11 Three main tools
  12. 12 Online primal-dual method
  13. 13 Complementary CDF viewpoint
  14. 14 Updating the dual variables
  15. 15 Edge-weighted matching algorithm
  16. 16 Analysis roadmap
  17. 17 Factor-revealing linear program
  18. 18 Open problems

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.