An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations

Speaker: Jonathan Kelner , MIT

Date: Tuesday, October 01, 2013

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

Public: Yes

Location: 32-141

Event Type:

Room Description:

Host:

Contact:

Relevant URL: https://www.eecs.mit.edu/news-events/calendar/events/almost-linear-time-algorithm-approximate-max-flow-undirected-graphs-and

Speaker URL: None

Speaker Photo:
None

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

Reminder Subject: TALK: An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations

Abstract:

In this talk, I will describe a new framework for approximately solving flow problems in capacitated, undirected graphs, and I will apply it to provide asymptotically faster algorithms for the maximum s-t flow and maximum concurrent multicommodity flow problems. For graphs with n vertices and m edges, it allows us to find an epsilon-approximate maximum s-t flow in time O(m^{1+o(1)} epsilon^{-2}), improving on the previous best bound of Õ(mn^{1/3}poly(1/?)). Applying the same framework in the multicommodity setting solves a maximum concurrent multicommodity flow problem with k commodities in O(m^{1+o(1)}epsilon^{-2}k^2) time, improving on the existing bound of Õ(m^{4/3} poly(k,1/epsilon).

In describing these algorithms, I will discuss several new technical tools that may be of independent interest:

* a non-Euclidean generalization of gradient descent, bounds on its performance, and a way to use this to reduce approximate maximum flow and maximum concurrent flow to oblivious routing;

* the definition and efficient construction of a new type of flow sparsifier that ameliorates the longstanding gap between the algorithmic efficacy of sparsification on flow and cut problems; and

* the first almost-linear-time construction of an O(m^{o(1)})-competitive oblivious routing scheme.

This is joint work with Yin Tat Lee, Lorenzo Orecchia, and Aaron Sidford.

Research Areas:

Impact Areas:

This event is not part of a series.

Created by Jonathan Adam Kelner at Monday, September 23, 2013 at 4:33 PM.