Faster Flow Algorithms using Variations of Electrical Flows

April 18, 2012

ABSTRACT:

The maximum flow problem as well as its generalizations to multiple commodities are well-studied problems. This talk aims to give a brief overview of the recent advances in approximate maxflow algorithms by Christiano et al, and describe ongoing work in the following two directions:

1. An algorithm that finds $1-\epsilon$ approximate solutions to $k$-commodity flow problems in time $\tilde{O}(m^{4/3} poly(k,\epsilon^{-1}))$. We study the key linear systems that are generated by quadratically coupled flows, and show that the algorithm can be tailored to generate ones that can be preconditioned and solved efficiently using graph Laplacians.

2. Speedups of the Christiano et al. framework in undirected graphs with good separator structures, such as bounded genus, minor free and geometric graphs. Specifically given a well-separable graph with $n$ vertices, our algorithm finds an $1-\epsilon$ approximate maximum flow in time $\tilde{O}(m^{6/5} poly(\epsilon^{-1}))$. Key to this algorithm is the use of grouped $L_2$ flows that exist between maximum flows and electrical flows, as well as fast routines for computing spectral vertex sparsifiers.

This is joint work with Jon Kelner and Gary Miller.

The maximum flow problem as well as its generalizations to multiple commodities are well-studied problems. This talk aims to give a brief overview of the recent advances in approximate maxflow algorithms by Christiano et al, and describe ongoing work in the following two directions:

1. An algorithm that finds $1-\epsilon$ approximate solutions to $k$-commodity flow problems in time $\tilde{O}(m^{4/3} poly(k,\epsilon^{-1}))$. We study the key linear systems that are generated by quadratically coupled flows, and show that the algorithm can be tailored to generate ones that can be preconditioned and solved efficiently using graph Laplacians.

2. Speedups of the Christiano et al. framework in undirected graphs with good separator structures, such as bounded genus, minor free and geometric graphs. Specifically given a well-separable graph with $n$ vertices, our algorithm finds an $1-\epsilon$ approximate maximum flow in time $\tilde{O}(m^{6/5} poly(\epsilon^{-1}))$. Key to this algorithm is the use of grouped $L_2$ flows that exist between maximum flows and electrical flows, as well as fast routines for computing spectral vertex sparsifiers.

This is joint work with Jon Kelner and Gary Miller.