BEGIN:VCALENDAR
VERSION:2.0
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
BEGIN:VEVENT
CATEGORIES:Conferences/Seminars/Lectures
DESCRIPTION:Featured Speaker : Guanghao Ye (MIT Mathematics)\n\nTitle : N
ested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time\n\n
Abstract : We present a nearly-linear time algorithm for finding a minimum-
cost flow in planar graphs with polynomially bounded integer costs and capa
cities. The previous fastest algorithm for this problem is based on interio
r-point methods (IPMs) and works for general sparse graphs in $O(n^{1.5}\te
xt{poly}(\log n))$ time [Daitch-Spielman\, STOC'08]. Our results immediatel
y 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.
DTEND:20220217T234500Z
DTSTAMP:20230322T041722Z
DTSTART:20220217T230000Z
GEO:42.358262;-71.090045
LOCATION:Building 2\, 2-132
SEQUENCE:0
SUMMARY:Simple Person's Applied Math Seminar
UID:tag:localist.com\,2008:EventInstance_39183401880523
URL:https://calendar.mit.edu/event/simple_persons_applied_math_seminar_2022
0217
END:VEVENT
END:VCALENDAR