Maximum Flow and Minimum-Cost Flow in Almost Linear Time
Rasmus Kyng (ETH Zurich)
TCS+ April 20th, 2022
Joint work with
Li Chen
GaTech
Yang Liu
Stanford
Richard Peng
UWaterloo
Max Probst Gutenberg
ETH Zurich
Sushant Sachdeva
UToronto
Apples on Trains?
2
Some cities have a surplus of apples, others a deficit.
How can we most cheaply send the surplus apples to cities with a deficit?
city = vertex
train route = edge
Train routes are directed and have
a cost (fuel spent per ton of apples) and
a capacity (tonnes apples per day)
Is this optimal?
No.
Improving our Solution?
3
Network with “undo” edges?
“the residual network w.r.t. to the given flow”
Finding a Feasible Initial Flow?
4
Add “fake” edge with high capacity and cost
Negative Cycles
5
Cost only: “Transshipment” Tolstoi ’30 Negative cycles
Capacities only: “Maximum Flow” Harris-Ross, Ford-Fulkerson ’55 Path augmentation
Both: “Minimum Cost Flow”
Trouble:
Finding these negative cost cycles is difficult ☹
We might need many cycle updates?
By finding negative cost cycles in the residual graph we can improve our solution.
If there are no negative cost cycles, the solution is optimal.
Maximum Flow Running Times
Meanwhile, in a Different World
7
Linear Programming
Dantzig ’47 The Simplex Algorithm
Initial solution
Exponential time ☹
Khachiyan ’79 Ellipsoid Method
Karmarkar ’84 Interior Point Method (IPM)
Renegar ’88 Path-Following IPM
Numerical Algorithms
Meanwhile, in a Different World
8
Linear Programming
Karmarkar ’84 Interior Point Method (IPM)
Renegar ’88 Path-Following IPM
Meanwhile, in a Different World
9
Karmarkar ’84 Interior Point Method (IPM)
Renegar ’88 Path-Following IPM
Linear Programming
Meanwhile, in a Different World
10
Karmarkar ’84 Interior Point Method (IPM)
Renegar ’88 Path-Following IPM
Linear Programming
Meanwhile, in a Different World
11
Daitch-Spielman ’08: New maxflow algorithm
Linear Programming
Meanwhile, in a Different World
Daitch-Spielman ’08: New maxflow algorithm
Linear Programming
Madry ’16: Send an electrical flow where?
In the residual graph, but undirectified
Meanwhile, in a Different World
13
Daitch-Spielman ’08: New maxflow algorithm
Linear Programming
Instead of adjusting one cycle,
the update touches every edge
15 years of increasingly clever global updates
Maximum Flow Running Times
reduce IPM inner update cost:
dynamic electrical flow
reduce IPM
outer loop iterations
BLNPSSSW’20 Brand, Lee, Nanongkai, Peng, Saranurak, Sidford, Song, Wang
BLLSSSW’21 Brand, Lee, Liu, Saranurak, Sidford, Song, Wang
BGJLLPS’22 Brand, Gao, Lee, Liu, Peng, Sidford
Flow Optimization
15
Maximum Flow Linear Program
Minimum Cost Flow Linear Program
Convex Flow Program
Applications: Almost-Linear Time Algorithms
(Min-cost) Bi-partite matching
Worker assignment
Optimal transport
Directed flows with vertex capacities / costs
Undirected vertex connectivity
Negative weight shortest paths
Flow diffusion
…
Karmarkar-style IPM for Flow
17
Karmarkar-style IPM for Flow
18
Forward edge
residual capacity
Backward edge
residual capacity
Karmarkar-style IPM for Flow
19
undirectified residual capacity
Karmarkar-style IPM for Flow
20
Taylor expansion upper bound
Karmarkar-style IPM for Flow
21
If
Std. L2 IPM
Our L1 IPM
Exercise: min-ratio circulation is always realized by a simple cycle
Similar L1 IPM: Wallacher & Zimmerman ‘92
Very Stable Min-Ratio Problems
22
If
How does our sequence of min-ratio cycle problems look?
Karmarkar-style IPM for Flow
23
Our L1 IPM
Adversary is not oblivious! ☹!?
Not a fully adaptive adversary!
No…
Comparing Three Algorithms for Min-Cost Flow
24
#Updates
#Time per update
Daitch-Spielman ’08
Our new algorithm
almost constant?!
Data structure leverages
powerful approximation theory
for undirected graphs
Goldberg-Tarjan ‘87
Update Type
undirected electrical flow
undirected negative cycle
+ approximate very crudely
directed negative cycle
Warm-up: A Single Approximate Min-Ratio Cycle using Random Trees
25
Probabilistic low-stretch trees
Alon-Karp-Peleg-West ‘95,
Elkin-Emek-Spielman-Teng ‘05, Abraham-Bartal-Neiman ‘09
Overall Algorithm
26
Min-Ratio Data Structure
Thank you for listening! Questions?���arxiv.org/abs/2203.00671
28
Li Chen
GaTech
Yang Liu
Stanford
Richard Peng
UWaterloo
Max Probst Gutenberg
ETH Zurich
Sushant Sachdeva
UToronto
Co-authors
Bonus: Edge Sparsification and Spanner Cycles
Bonus: Edge Sparsification and Spanner Cycles
Spanner
cycles
Spanner
embedding
Lemma
Either some spanner cycle is a good min-ratio cycle
OR
Challenge
We maintain explicit embeddings
of all edges into spanner