On Dynamic Graph Approximations: The case of j-Trees

on YouTube ↗53m

" summary

Proves a dynamic data structure that maintains Madry-style j‑tree approximations so fully dynamic s–t max‑flow queries run with truly sublinear updates: about n^{2/3} update time and nearly log n approximation. Construction uses multiplicative‑weights over spanning‑subgraph oracles, samples O(log n) j‑trees, applies portal projection to turn high‑load edges into a small j‑core, and relies on dynamic tree data structures; initial j‑tree structure builds in about m n / j time and supports amortized terminal additions.

AI-written summary · about

" chapters (6)

1. 0:00Introduction
2. 10:48Dynamic max flow algorithms
3. 20:39Tree-based j-trees
4. 33:47Maintaining j-trees for max flow
5. 44:42Constructing j-trees and edge loads
6. 51:34Conclusion