A new approach to computing maximum flows using electrical flows
Yin Tat Leea b, Satish B. Raoc, Nikhil Srivastavad e
- aMIT, Cambridge, MA, USA
- bMIT, Cambridge MA, USA#TAB#
- cUC Berkeley, Berkeley, CA, USA
- dMicrosoft Research, Bangalore, India
- eMicrosoft Research, Bangalore, India#TAB#
Papers open inside SciRah from the original publisher or repository; SciRah never hosts them.
Abstract
We give an algorithm which computes a (1-ε)-approximately maximum st-flow in an undirected uncapacitated graph in time O(1/ε√m/F⋅ m log2 n) where F is the flow value. By trading this off against the Karger-Levine algorithm for undirected graphs which takes ~O(m+nF) time, we obtain a running time of ~O(m n1/3/ε2/3) for uncapacitated graphs, improving the previous best dependence on ε by a factor of O(1/ε3). Like the algorithm of Christiano, Kelner, Madry, Spielman and Teng, our algorithm reduces the problem to electrical flow computations which are carried out in linear time using fast Laplacian solvers. However, in contrast to previous work, our algorithm does not reweight the edges of the graph in any way, and instead uses local (i.e., non s-t) electrical flows to reroute the flow on congested edges. The algorithm is simple and may be viewed as trying to find a point at the intersection of two convex sets (the affine subspace of st-flows of value F and the l∞ ball) by an accelerated version of the method of alternating projections due to Nesterov.
TL;DRAn algorithm which computes a (1-ε)-approximately maximum st-flow in an undirected uncapacitated graph in time O(1/ε√m/F⋅ m log2 n) where F is the flow value and the minimizer is related to an approximate blocking flow is shown. (Semantic Scholar)