Minimum cost flow in the CONGEST model
From MaRDI portal
Publication:6148076
DOI10.1007/978-3-031-32733-9_18arXiv2304.01600OpenAlexW4377971925MaRDI QIDQ6148076
Publication date: 11 January 2024
Published in: Structural Information and Communication Complexity (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2304.01600
Graph theory (including graph drawing) in computer science (68R10) Computer system organization (68Mxx) Communication complexity, information complexity (68Q11)
Cites Work
- Unnamed Item
- Unnamed Item
- A polynomial-time algorithm, based on Newton's method, for linear programming
- Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
- Single-source shortest paths in the CONGEST model with improved bounds
- A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction
- Computational Advertising: Techniques for Targeting Relevant Ads
- Uniform Sampling for Matrix Approximation
- Randomized Algorithms for Matrices and Data
- Extensions of Lipschitz mappings into a Hilbert space
- An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem
- Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
- Distributed Computing: A Locality-Sensitive Approach
- Near-Optimal Distributed Maximum Flow
- Distributed Algorithms for Planar Networks II: Low-Congestion Shortcuts, MST, and Min-Cut
- Approximate Undirected Maximum Flows in O(mpolylog(n)) Time
- Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in Õ (m10/7 log W) Time (Extended Abstract)
- Distributed Verification and Hardness of Distributed Approximation
- Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
- Distributed Approximate Maximum Matching in the CONGEST Model.
- Faster parallel algorithm for approximate shortest path
- Parallel approximate undirected shortest paths via low hop emulators
- Faster energy maximization for faster maximum flow
- An efficient parallel solver for SDD linear systems
- Solving SDD linear systems in nearly m log 1/2 n time
- Sparsified Cholesky and multigrid solvers for connection laplacians
- An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
- Approaching Optimality for Solving SDD Linear Systems
- A Nearly-m log n Time Solver for SDD Linear Systems
- A simple, combinatorial algorithm for solving SDD systems in nearly-linear time
- Graph Sparsification by Effective Resistances
- Almost universally optimal distributed Laplacian solvers via low-congestion shortcuts
This page was built for publication: Minimum cost flow in the CONGEST model
