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

Faculty Advisor:

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.

Link to Microsoft Teams meeting:
https://teams.microsoft.com/l/meetup-join/19%3ameeting_MjY0NmJhNWMtMDdkNC00ZWIxLTgzMWMtMjExNjZiYTA3YmE2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%22febce5be-d427-430f-b9d5-0bab6673a9ed%22%7d

Speaker Bio:

Host Faculty: Dr. Anand Louis