Name
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 + root n) . n(o(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 bound of O(n(2)), and it nearly matches the (Omega) over tilde (D + root n)-round complexity lower bound. The development of the algorithm entails two subresults of independent interest: (i) A (D + root n) . n(o(1))-round distributed construction of a spanning tree of average stretch n(o(1)). (ii) A (D + root n) . n(o(1))-round distributed construction of an n(o(1))-congestion approximator consisting of the cuts induced by O(logn) virtual trees. The distributed representation of the cut approximator allows for evaluation in (D + root n) n(o(1)) rounds. All our algorithms make use of randomization and succeed with high probability. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1137/17M113277X | SIAM JOURNAL ON COMPUTING |
Keywords | Field | DocType |
CONGEST model,congestion approximator,approximation algorithm,gradient descent | Discrete mathematics,Data structure,Approximation algorithm,Combinatorics,Gradient descent,Distributed algorithm,Maximum flow problem,Mathematics | Journal |
Volume | Issue | ISSN |
47 | 6 | 0097-5397 |
Citations | PageRank | References |
4 | 0.43 | 15 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mohsen Ghaffari | 1 | 452 | 44.89 |
| Andreas Karrenbauer | 2 | 133 | 20.21 |
| Fabian Kuhn | 3 | 2709 | 150.17 |
| Christoph Lenzen | 4 | 584 | 40.61 |
| Boaz Patt-shamir | 5 | 1347 | 105.94 |