Near-optimal distributed maximum flow

DOI10.1137/17M113277XMaRDI QIDQ4561245zbMATH OpenOpenAlexWikidataFDO

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

Publication date 5 December 2018

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/17m113277x

zbMATH Keywords

\textsf{CONGEST} modelapproximation algorithmcongestion approximatorgradient descent

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Distributed algorithms (68W15) Approximation algorithms (68W25)

Recommendations

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

Cites work

• A Graph-Theoretic Game and Its Application to the k-Server Problem
• A note on efficient aggregate queries in sensor networks
• A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
• An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations
• Beyond the flow decomposition barrier
• Decentralized maximum-flow protocols
• Distributed algorithms for multicommodity flow problems via approximate steepest descent framework
• Distributed Computing: A Locality-Sensitive Approach
• Distributed verification and hardness of distributed approximation
• Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs
• Fast Approximation Algorithms for Fractional Packing and Covering Problems
• Fast distributed construction of k-dominating sets and applications
• scientific article; zbMATH DE number 5485537 (Why is no real title available?)
• Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks
• Introductory lectures on convex optimization. A basic course.
• Near-optimal distributed maximum flow (extended abstract)
• Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems
• Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs
• Network flows. Theory, algorithms, and applications.
• On the history of the transportation and maximum flow problems
• Randomized approximation schemes for cuts and flows in capacitated graphs
• Reducing complexities of the distributed max-flow and breadth-first-search algorithms by means of network synchronization
• Stateless distributed gradient descent for positive linear programs
• The multiplicative weights update method: a meta-algorithm and applications

Cited in

(9)

• Safe and stabilizing distributed multi-path cellular flows
• Near-optimal distributed maximum flow (extended abstract)
• Fast Distributed Approximation for Max-Cut
• Minimum cost flow in the CONGEST model
• Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions
• Brief Announcement: Minimum Cost Maximum Flow in the CONGEST Model
• Brief Announcement: The Laplacian Paradigm in Deterministic Congested Clique
• Finding a small vertex cut on distributed networks
• Title not available (Why is no real title available?)

This page was built for publication: Near-optimal distributed maximum flow

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