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

Conferences/Seminars/Lectures

Events By Interest

Academic

Events By Audience

MIT Community

Events By School

School of Science

Tags

aldixon, Applied Mathematics Seminar

Website

https://math.mit.edu/seminars/spams/

Department
Department of Mathematics
Hashtag

#Mathematics

Contact Email

aldixon@mit.edu

Add to my calendar

Recent Activity