Simple Person's Applied Math Seminar

Featured Speaker :  Guanghao Ye (MIT Mathematics)

Title :  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.