Paper Info
Title
Near-Optimal Distributed Maximum Flow: Extended Abstract
Abstract
We present a near-optimal distributed algorithm for (1+o(1))-approximation of single-commodity maximum flow in undirected weighted networks that runs in (D+ √n)⋅ no(1) communication rounds in the Congest model. Here, n and D denote the number of nodes and the network diameter, respectively. This is the first improvement over the trivial O(m) time bound, and it nearly matches the Ω(D+√n) round complexity lower bound. The algorithm contains two sub-algorithms of independent interest, both with running time (D+√n)⋅ no(1): Distributed construction of a spanning tree of average stretch no(1). Distributed construction of an no(1)-congestion approximator consisting of the cuts induced by O(log n) virtual trees. The distributed representation of the cut approximator allows for evaluation in (D+√n)⋅ no(1) rounds. All our algorithms make use of randomization and succeed with high probability.
Year
DOI
Venue
2015
10.1145/2767386.2767440
ACM Symposium on Principles of Distributed Computing
Field
DocType
Citations 
Round complexity,Binary logarithm,Gradient descent,Computer science,Upper and lower bounds,Theoretical computer science,Distributed algorithm,Spanning tree,Maximum flow problem,Distributed representation,Distributed computing
Conference
8
PageRank 
References 
Authors
0.52
19
5
Name
Order
Citations
PageRank
Mohsen Ghaffari145244.89
Andreas Karrenbauer213320.21
Fabian Kuhn32709150.17
Christoph Lenzen458440.61
Boaz Patt-shamir51347105.94