Near-Optimal Distributed Maximum Flow
From MaRDI portal
Publication:4561245
DOI10.1137/17M113277XzbMath1404.68205OpenAlexW1861736669WikidataQ128861642 ScholiaQ128861642MaRDI QIDQ4561245
Boaz Patt-Shamir, Andreas Karrenbauer, Mohsen Ghaffari, Fabian Kuhn, Christoph Lenzen
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
Network design and communication in computer systems (68M10) Approximation algorithms (68W25) Distributed algorithms (68W15)
Related Items (4)
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
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs
- A note on efficient aggregate queries in sensor networks
- Introductory lectures on convex optimization. A basic course.
- Near-Optimal Distributed Maximum Flow
- Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks
- Distributed algorithms for multicommodity flow problems via approximate steepest descent framework
- Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems
- Beyond the flow decomposition barrier
- Stateless Distributed Gradient Descent for Positive Linear Programs
- Reducing complexities of the distributed max-flow and breadth-first-search algorithms by means of network synchronization
- Decentralized maximum-flow protocols
- A Graph-Theoretic Game and Its Application to the k-Server Problem
- Distributed Computing: A Locality-Sensitive Approach
- Fast Approximation Algorithms for Fractional Packing and Covering Problems
- Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs
- A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
- Fast distributed construction of k-dominating sets and applications
- An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
- Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs
- Distributed verification and hardness of distributed approximation
- On the history of the transportation and maximum flow problems
This page was built for publication: Near-Optimal Distributed Maximum Flow