BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//project/author//NONSGML v1.0//EN
CALSCALE:GREGORIAN
BEGIN:VEVENT
DTEND:20201113T120000Z
UID:704971bb19247d199d0b9cbb374d4bd0-107
DTSTAMP:19700101T120011Z
DESCRIPTION:An O(m^{4/3+o(1)}) algorithm for exact unit-capacitated max flow
URL;VALUE=URI:https://www.csa.iisc.ac.in/newweb/event/107/an-om4-3o1-algorithm-for-exact-unit-capacitated-max-flow/
SUMMARY: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="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">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</a>
DTSTART:20201113T120000Z
END:VEVENT
END:VCALENDAR