Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time

Abstract: We present a nearly-linear time algorithm for finding a minimum-cost flow in planar graphs with polynomially bounded integer costs and capacities. The previous fastest algorithm for this problem is based on interior-point methods (IPMs) and works for general sparse graphs in $O(n^{1.5}\text{poly}(\log n))$ time [Daitch-Spielman, STOC'08]. Our results immediately extend to all families of separable graphs. This is joint work with Sally Dong, Yu Gao, Gramoz Goranci, Yin Tat Lee, Richard Peng, and Sushant Sachdeva.

Computer scienceMathematicsPhysics

Audience: researchers in the topic

MIT Simple Person's Applied Mathematics Seminar