Submodular Unsplittable Flow on Trees

on YouTube ↗29m

" summary

Gives a concrete algorithmic pipeline that yields a K log n approximation for submodular unsplittable flow on trees: reduce to intersecting instances (losing a log), partition the tree into K upward paths, project tasks to a rectangle-as-task geometric view, write an LP with height variables, then use independent randomized selection and an alteration that rejects any selected task with probability ≤1/2 per path. Extends to submodular objectives via the contention-resolution scheme and handles large capacities by discretizing heights.

AI-written summary · about

" chapters (13)

1. 0:00Intro
2. 0:24Preliminaries
3. 4:13High-level idea
4. 5:50Reduction to intersecting instances
5. 7:48Partitioning the tree T into paths
6. 10:33Geometric viewpoint
7. 12:50Integer program
8. 14:52LP relaxation
9. 15:27Selection phase
10. 16:24Alteration phase
11. 17:57Algorithm analysis
12. 19:47Removing restriction on edge capacities
13. 20:44Submodular objective: CR scheme