research-article

Near-Optimal Distributed Maximum Flow: Extended Abstract

Authors:

Mohsen Ghaffari,

Andreas Karrenbauer,

Christoph Lenzen,

Boaz Patt-ShamirAuthors Info & Claims

PODC '15: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing

Pages 81 - 90

https://doi.org/10.1145/2767386.2767440

Published: 21 July 2015 Publication History

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)⋅ 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 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)⋅ n^o(1): Distributed construction of a spanning tree of average stretch n^o(1). Distributed construction of an n^o(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)⋅ n^o(1) rounds.

All our algorithms make use of randomization and succeed with high probability.

References

[1]

I. Abraham, Y. Bartal, and O. Neiman. Nearly tight low stretch spanning trees. In Proc. of the Symp. on Found. of Comp. Sci. (FOCS), pages 781--790. IEEE, 2008.

Digital Library

[2]

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network Flows. Prentice-Hall, Engelwood Cliffs, New Jersey, 1993.

Digital Library

[3]

N. Alon, R. M. Karp, D. Peleg, and D. West. A graph-theoretic game and its application to the k-server problem. SIAM Journal on Computing, 24(1):78--100, 1995.

Digital Library

[4]

S. Arora, E. Hazan, and S. Kale. The multiplicative weights update method: a meta-algorithm and applications. Theory of Computing, 8(1):121--164, 2012.

[5]

B. Awerbuch. Reducing complexities of the distributed max-flow and breadth-first-search algorithms by means of network synchronization. Networks, 15(4):425--437, Winter 1985.

[6]

B. Awerbuch and R. Khandekar. Stateless distributed gradient descent for positive linear programs. SIAM Journal on Computing, 38(6):2468--2486, 2009.

Digital Library

[7]

B. Awerbuch, R. Khandekar, and S. Rao. Distributed algorithms for multicommodity flow problems via approximate steepest descent framework. ACM Transactions on Algorithms, 9(1):3, 2012.

Digital Library

[8]

B. Awerbuch and T. Leighton. Improved approximation algorithms for the multi-commodity flow problem and local competitive routing for dynamic networks. In Proc. 26th Ann. ACM Symp. on Theory of Computing, pages 487--496, 1994.

Digital Library

[9]

A. A. Benczúr and D. R. Karger. Randomized approximation schemes for cuts and flows in capacitated graphs. CoRR, cs.DS/0207078, 2002.

[10]

G. E. Blelloch, A. Gupta, I. Koutis, G. L. Miller, R. Peng, and K. Tangwongsan. Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs. Theory Comput. Syst., 55(3):521--554, 2014.

Digital Library

[11]

A. Das Sarma, S. Holzer, L. Kor, A. Korman, D. Nanongkai, G. Pandurangan, D. Peleg, and R. Wattenhofer. Distributed verification and hardness of distributed approximation. In Proc. of the Symp. on Theory of Comp. (STOC), pages 363--372, 2011.

Digital Library

[12]

A. V. Goldberg and R. E. Tarjan. Efficient maximum flow algorithms. Commun. ACM, 57(8):82--89, August 2014.

Digital Library

[13]

I. Koutis. Simple parallel and distributed algorithms for spectral graph sparsification. In the Proceedings of the Symposium on Parallel Algorithms and Architectures, pages 61--66, 2014.

Digital Library

[14]

S. Kutten and D. Peleg. Fast distributed construction of k-dominating sets and applications. In the Proc. of the Int'l Symp. on Princ. of Dist. Comp. (PODC), pages 238--251, 1995.

Digital Library

[15]

A. Madry. Fast approximation algorithms for cut-based problems in undirected graphs. In Proc. of the Symp. on Found. of Comp. Sci. (FOCS), pages 245--254, 2010.

Digital Library

[16]

J. M. Marberg and E. Gafni. An O(n2 m1/2) distributed max-flow algorithm. In Int. Conf. on Parallel Processing, (ICPP'87), pages 213--216, 1987.

[17]

Y. Nesterov. Introductory lectures on convex optimization, volume 87. Springer Science & Business Media, 2004.

Digital Library

[18]

Y. Nesterov. Smooth minimization of non-smooth functions. Mathematical programming, 103(1):127--152, 2005.

Digital Library

[19]

D. Peleg. Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2000.

[20]

S. A. Plotkin, D. B. Shmoys, and É. Tardos. Fast approximation algorithms for fractional packing and covering problems. Mathematics of Operations Research, 20(2):257--301, 1995.

Digital Library

[21]

H. Racke. Optimal hierarchical decompositions for congestion minimization in networks. In Proc. of the Symp. on Theory of Comp. (STOC), pages 255--264, 2008.

Digital Library

[22]

A. Schrijver. On the history of the transportation and maximum flow problems. Mathematical Programming, 91(3):437--445, 2002.

Digital Library

[23]

A. Segall. Decentralized maximum-flow protocols. Networks, 12(3):213--230, Fall 1982.

[24]

J. Sherman. Nearly maximum flows in nearly linear time. In Proc. of the Symp. on Found. of Comp. Sci. (FOCS), pages 263--269, 2013.

Digital Library

[25]

N. E. Young. Sequential and parallel algorithms for mixed packing and covering. In Proc. of the Symp. on Found. of Comp. Sci. (FOCS), pages 538--546. IEEE, 2001.

Digital Library

Cited By

Haeupler BHershkowitz DSaranurak TSaha BServedio R(2023)Maximum Length-Constrained Flows and Disjoint Paths: Distributed, Deterministic, and FastProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585202(1371-1383)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585202
Anagnostides ILenzen CHaeupler BZuzic GGouleakis T(2023)Almost universally optimal distributed Laplacian solvers via low-congestion shortcutsDistributed Computing10.1007/s00446-023-00454-036:4(475-499)Online publication date: 31-Jul-2023
https://doi.org/10.1007/s00446-023-00454-0
KITAMURA NIZUMI T(2022)A Subquadratic-Time Distributed Algorithm for Exact Maximum MatchingIEICE Transactions on Information and Systems10.1587/transinf.2021EDP7083E105.D:3(634-645)Online publication date: 1-Mar-2022
https://doi.org/10.1587/transinf.2021EDP7083
Show More Cited By

Index Terms

Near-Optimal Distributed Maximum Flow: Extended Abstract
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Network flows
2. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis
      1. Network flows
  2. Randomness, geometry and discrete structures

Recommendations

Near-Optimal Distributed Maximum Flow

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+\sqrt{n})\cdot n^{o(1)}$ communication rounds in the CONGEST model. Here, $n$ and $D$ denote ...
Distributed approximation algorithms for weighted shortest paths
STOC '14: Proceedings of the forty-sixth annual ACM symposium on Theory of computing

A distributed network is modeled by a graph having n nodes (processors) and diameter D. We study the time complexity of approximating weighted (undirected) shortest paths on distributed networks with a O (log n) bandwidth restriction on edges (the ...
Near-Optimal Distributed Dominating Set in Bounded Arboricity Graphs
PODC'22: Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing

We describe a simple deterministic O(ε-1 log Δ) round distributed algorithm for (2α+ 1) (1 + ε) approximation of minimum weighted dominating set on graphs with arboricity at most α. Here Δ denotes the maximum degree. We also show a lower bound proving ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '15: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing

July 2015

508 pages

ISBN:9781450336178

DOI:10.1145/2767386

General Chair:
Chryssis Georgiou
University of Cyprus, Cyprus
,
Program Chair:
Paul G. Spirakis
University of Liverpool, UK & CTI, Greece

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 July 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Israel Ministry of Science Technology and Space
Max Planck Center for Visual Computing and Communication
Israel Science Foundation

Conference

PODC '15

Sponsor:

PODC '15: ACM Symposium on Principles of Distributed Computing

July 21 - 23, 2015

Donostia-San Sebastián, Spain

Acceptance Rates

PODC '15 Paper Acceptance Rate 45 of 191 submissions, 24%;

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
293
Total Downloads

Downloads (Last 12 months)23
Downloads (Last 6 weeks)0

Reflects downloads up to 15 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Haeupler BHershkowitz DSaranurak TSaha BServedio R(2023)Maximum Length-Constrained Flows and Disjoint Paths: Distributed, Deterministic, and FastProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585202(1371-1383)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585202
Anagnostides ILenzen CHaeupler BZuzic GGouleakis T(2023)Almost universally optimal distributed Laplacian solvers via low-congestion shortcutsDistributed Computing10.1007/s00446-023-00454-036:4(475-499)Online publication date: 31-Jul-2023
https://doi.org/10.1007/s00446-023-00454-0
KITAMURA NIZUMI T(2022)A Subquadratic-Time Distributed Algorithm for Exact Maximum MatchingIEICE Transactions on Information and Systems10.1587/transinf.2021EDP7083E105.D:3(634-645)Online publication date: 1-Mar-2022
https://doi.org/10.1587/transinf.2021EDP7083
Agarwal RRajakrishnan SShmoys DMilani AWoelfel P(2022)From Switch Scheduling to Datacenter SchedulingProceedings of the 2022 ACM Symposium on Principles of Distributed Computing10.1145/3519270.3538443(313-323)Online publication date: 20-Jul-2022
https://dl.acm.org/doi/10.1145/3519270.3538443
Forster SGoranci GLiu YPeng RSun XYe M(2022)Minor Sparsifiers and the Distributed Laplacian Paradigm2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS52979.2021.00099(989-999)Online publication date: Feb-2022
https://doi.org/10.1109/FOCS52979.2021.00099
Sengupta SPeri SAnjana P(2022)A Self-stabilizing Minimum Average Stretch Spanning Tree ConstructionNetworked Systems10.1007/978-3-031-17436-0_9(119-135)Online publication date: 17-May-2022
https://dl.acm.org/doi/10.1007/978-3-031-17436-0_9
Haeupler BWajc DZuzic GKhuller SVassilevska Williams V(2021)Universally-optimal distributed algorithms for known topologiesProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3451081(1166-1179)Online publication date: 15-Jun-2021
https://dl.acm.org/doi/10.1145/3406325.3451081
Dory MEfron YMukhopadhyay SNanongkai DKhuller SVassilevska Williams V(2021)Distributed weighted min-cut in nearly-optimal timeProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3451020(1144-1153)Online publication date: 15-Jun-2021
https://dl.acm.org/doi/10.1145/3406325.3451020
Bernstein ANanongkai D(2021)Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear TimeSIAM Journal on Computing10.1137/20M131278252:2(STOC19-112-STOC19-127)Online publication date: 23-Nov-2021
https://doi.org/10.1137/20M1312782
Haeupler BIzumi TZuzic G(2021)Low-Congestion shortcuts without embeddingDistributed Computing10.1007/s00446-020-00383-234:1(79-90)Online publication date: 1-Feb-2021
https://dl.acm.org/doi/10.1007/s00446-020-00383-2
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents