Seminars

View all Seminars  |  Download ICal for this event

An O(m^{4/3+o(1)}) algorithm for exact unit-capacitated max flow

Series: Theory Seminar Series: On-Line

Speaker: Mr. Tarun Kathuria Ph.D Student University of California Berkeley

Date/Time: Nov 13 11:00:00

Location: Microsoft Teams - On-Line

Abstract:
In this talk, I will present an algorithm for computing s-t max flows in O(m^{4/3+o(1)}) time in unit capacity graphs. The algorithm is inspired by potential reduction Interior Point Methods for linear programming. Instead of using scaled gradient/Newton steps of a potential function, we consider minimizing the potential function exactly and show how this allows us to directly find a centered point efficiently. Then using the weighted central path framework of Madry and Liu-Sidford, we show that our steps also benefit from maximizing weights carefully, which can be efficiently solved using work of Kyng et al., which allows us to get the desired runtime.
<br>
<br>
Link to Microsoft Teams meeting:
<br>
<a href="Link

Host Faculty: Dr. Anand Louis