Simple Person's Applied Math Seminar

Thursday, February 17, 2022 at 6:00pm to 6:45pm

Building 2, 2-132
182 MEMORIAL DR, Cambridge, MA 02139

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.

Event Type


Events By Interest


Events By Audience

MIT Community

Events By School

School of Science


aldixon, Applied Mathematics Seminar


Department of Mathematics


Contact Email

Add to my calendar

Recent Activity