A&C Seminar: Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg-Rao

Speaker: Yang P. Liu , Stanford

Date: Wednesday, March 31, 2021

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: https://mit.zoom.us/j/97637459251

Event Type: Seminar

Room Description:

Host: Quanquan Liu, MIT

Contact: Quanquan Liu, quanquan@csail.mit.edu

Relevant URL: https://mit.zoom.us/j/97637459251

Speaker URL: https://yangpliu.github.io/

Speaker Photo:
None

Reminders to: theory-seminars@csail.mit.edu, seminars@csail.mit.edu

Reminder Subject: TALK: Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg-Rao

Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg-Rao

We give an algorithm for computing exact maximum flows on graphs with m edges and integer capacities in the range [1, U] in O(m^(3/2-1/328) log U) time. For sparse graphs with polynomially bounded integer capacities, this is the first improvement over the O(m^1.5 log U) time bound from [Goldberg-Rao JACM `98].

Our algorithm revolves around dynamically maintaining the augmenting electrical flows at the core of the interior point method based algorithm from [Madry JACM `16]. This entails designing data structures that, in limited settings, return edges with large electric energy in a graph undergoing resistance updates.

Based on joint work with Yu Gao and Richard Peng.

Research Areas:
Algorithms & Theory, AI & Machine Learning

Impact Areas:
Big Data

See other events that are part of the Algorithms and Complexity Seminar 2021.

Created by Quanquan Liu at Saturday, March 27, 2021 at 1:16 AM.