BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Guanghao Ye (MIT)
DTSTART:20220217T223000Z
DTEND:20220218T000000Z
DTSTAMP:20260423T021051Z
UID:SPAMS/9
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/SPAMS/9/">Ne
 sted Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time</a>
 \nby Guanghao Ye (MIT) as part of MIT Simple Person's Applied Mathematics 
 Seminar\n\nLecture held in Room: 2 - 132 in the Simons Building.\n\nAbstra
 ct\nWe present a nearly-linear time algorithm for finding a minimum-cost f
 low in planar graphs with polynomially bounded integer costs and capacitie
 s. The previous fastest algorithm for this problem is based on interior-po
 int methods (IPMs) and works for general sparse graphs in $O(n^{1.5}\\text
 {poly}(\\log n))$ time [Daitch-Spielman\, STOC'08]. Our results immediatel
 y extend to all families of separable graphs. This is joint work with Sall
 y Dong\, Yu Gao\, Gramoz Goranci\, Yin Tat Lee\, Richard Peng\, and Sushan
 t Sachdeva.\n
LOCATION:https://researchseminars.org/talk/SPAMS/9/
END:VEVENT
END:VCALENDAR