Online Algorithms with Recourse

on YouTube ↗33m

" summary

Greedy online load balancing is Θ(log m) worst case, but allowing limited recourse changes the picture: an edge‑orientation rule that flips all incoming edges when a vertex hits in‑degree three achieves max indegree two with 3 amortized flips per arrival; matching via shortest augmenting paths gives constant competitive ratio with constant amortized reassignments, and with general job sizes a fractional‑rounding scheme yields log log N competitive while keeping constant amortized moves. Open gaps: non‑amortized constant/constant and fully dynamic bounds remain unresolved.

AI-written summary · about

" chapters (17)

1. 0:00Intro
2. 1:12Online load balancing
3. 3:10Edge Orientation Problem
4. 4:52online spanning tree
5. 5:42Greedy Algorithm
6. 6:10Case for competitive analysis
7. 8:06Edge Orientation with Recourse
8. 8:40Online algorithms with recourse
9. 11:17Brodal-Fagerberg Algorithm
10. 15:34Load Balancing with Recourse
11. 19:24Proof Idea
12. 22:52Load Balancing with Arbitrary Processing Time
13. 24:37Open Problems and Extensions
14. 26:06Online Steiner tree(with recourse)
15. 27:14Algorithm Idea
16. 28:48Number of swaps
17. 31:25Conclusion