BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1258
DTSTAMP:20230914T125956Z
SUMMARY:Almost linear time algorithms for max-flow and more
DESCRIPTION:Speaker: Sushant Sachdeva (University of Toronto)\n\nAbstract:
\nWe give the first almost-linear time algorithm for computing exact maxim
um flows and minimum-cost flows on directed graphs. By well known reductio
ns\, this implies almost-linear time algorithms for several problems inclu
ding bipartite matching\, optimal transport\, and undirected vertex connec
tivity.\n\nOur algorithm is designed using a new Interior Point Method (IP
M) that builds the flow as a sequence of almost-linear number of approxima
te undirected minimum-ratio cycles\, each of which is computed and process
ed very efficiently using a new dynamic data structure.\n\nOur framework e
xtends to give an almost-linear time algorithm for computing flows that mi
nimize general edge-separable convex functions to high accuracy. This give
s the first almost-linear time algorithm for several problems including en
tropy-regularized optimal transport\, matrix scaling\, p-norm flows\, and
Isotonic regression.\n\nJoint work with Li Chen\, Rasmus Kyng\, Yang Liu\,
Richard Peng\, and Maximilian Probst Gutenberg.\n\nBio: Sushant Sachdeva
is a faculty member at the CS dept. at the University of Toronto and a Vec
tor Institute affiliate. He is interested in algorithms\, and its connecti
ons to optimization\, machine learning\, and statistics. His recent resear
ch focus has been the design of fast algorithms for graph problems. https:
//www.cs.toronto.edu/~sachdeva/\n
URL:https://www.tcs.tifr.res.in/web/events/1258
DTSTART;TZID=Asia/Kolkata:20221222T143000
DTEND;TZID=Asia/Kolkata:20221222T153000
LOCATION:A-201 and Zoom
END:VEVENT
END:VCALENDAR