Computing Cut-Based Hierarchical Decompositions in Almost Linear Time

on YouTube ↗55m

" summary

Constructs a flow sparsifier that is a tree for k-terminal graphs and proves it yields an oblivious routing with similar competitive ratio; quality is roughly O(log^2 k · log^2 n) (quality unfortunately still depends on n). Algorithm builds a hierarchical decomposition using a KRV cut-matching style scheme and runs in almost-linear time by making only a polylog many approximate max-flows (uses Sherman/Kelner routines and ultrasparsification).

AI-written summary · about

" chapters (14)

1. 0:00Intro
2. 0:41Cut Sparsifiers/Flow Sparsifiers
3. 10:17Previous Work
4. 13:21Oblivious Routing Scheme from Tree
5. 16:53Hierarchical Decompositions & Oblivious Routing
6. 18:12Oblivious Routing Scheme - A Single Cluster S
7. 23:17Recursive Approach for a Single Tree
8. 26:25New Approach
9. 33:25Routing Along a Single Cluster
10. 38:09Simple Algorithm
11. 42:40Improvement?
12. 44:11Adapted KRV.framework
13. 48:32Improvement by Richard Peng
14. 50:53Conclusions/Problems