Near-optimal distributed maximum flow (extended abstract)

DOI10.1145/2767386.2767440MaRDI QIDQ2796244zbMATH OpenOpenAlexWikidataFDO

Authors Mohsen Ghaffari, Andreas Karrenbauer, Fabian Kuhn, Christoph Lenzen, Boaz Patt-Shamir

Publication date 23 March 2016

Published in Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1508.04747

zbMATH Keywords

distributed computingmaximum flowgradient descentcongest modeldistributed congestion approximator

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Deterministic network models in operations research (90B10) Approximation algorithms (68W25) Distributed algorithms (68W15) Distributed systems (68M14)

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+sqrtn)cdot{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 $ildeOmega(D+sqrtn)$ round complexity lower bound. The development of the algorithm contains two results of independent interest: (i) A $(D+sqrtn)cdot{n}^{o(1)}$-round distributed construction of a spanning tree of average stretch $n^{o(1)}$. (ii) A $(D+sqrtn)cdot{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+sqrtn)cdot{n}^{o(1)}$ rounds. All our algorithms make use of randomization and succeed with high probability.

Recommendations

• Near-optimal distributed maximum flow
• An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations
• Almost-Tight Distributed Minimum Cut Algorithms
• Fast Distributed Approximation for Max-Cut
• Distributed minimum cut approximation

Cites work

• scientific article; zbMATH DE number 826255 (Why is no real title available?)
• Memorization and Association on a Realistic Neural Model

Cited in

(12)

• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• Fast Distributed Approximation for Max-Cut
• Near-optimal distributed maximum flow
• Distributed sparse cut approximation
• Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time
• Safe and stabilizing distributed multi-path cellular flows
• Low-congestion shortcuts without embedding
• Almost universally optimal distributed Laplacian solvers via low-congestion shortcuts
• Distributed model checking on graphs of bounded treedepth
• Finding a small vertex cut on distributed networks
• Maximum length-constrained flows and disjoint paths: distributed, deterministic, and fast
• Distributed MST and broadcast with fewer messages, and faster gossiping

This page was built for publication: Near-optimal distributed maximum flow (extended abstract)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2796244)