# 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
Events By School
Tags
Website
Department
Department of Mathematics
Hashtag

#Mathematics

Contact Email

aldixon@mit.edu