Minimum cost flow in the CONGEST model

DOI10.1007/978-3-031-32733-9_18MaRDI QIDQ6148076zbMATH OpenOpenAlexFDO

Authors Tijn de Vos

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

zbMATH Keywords

minimum cost flowCONGEST modelLP solver

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer system organization (68Mxx) Communication complexity, information complexity (68Q11)

Abstract: We consider the CONGEST model on a network with $n$ nodes, $m$ edges, diameter $D$, and integer costs and capacities bounded by $extpolyn$. In this paper, we show how to find an exact solution to the minimum cost flow problem in $n^{1/2+o(1)}(sqrtn+D)$ rounds, improving the state of the art algorithm with running time $m^{3/7+o(1)}(sqrtn{D}^{1/4}+D)$ [Forster et al. FOCS 2021], which only holds for the special case of unit capacity graphs. For certain graphs, we achieve even better results. In particular, for planar graphs, expander graphs, $n^{o(1)}$-genus graphs, $n^{o(1)}$-treewidth graphs, and excluded-minor graphs our algorithm takes $n^{1/2+o(1)}D$ rounds. We obtain this result by combining recent results on Laplacian solvers in the CONGEST model [Forster et al. FOCS 2021, Anagnostides et al. DISC 2022] with a CONGEST implementation of the LP solver of Lee and Sidford [FOCS 2014], and finally show that we can round the approximate solution to an exact solution. Our algorithm solves certain linear programs, that generalize minimum cost flow, up to additive error $epsilon$ in $n^{1/2+o(1)}(sqrtn+D)lo{g}^3(1/epsilon)$ rounds.

Cites work

• scientific article; zbMATH DE number 5485557 (Why is no real title available?)
• A Nearly-m log n Time Solver for SDD Linear Systems
• A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction
• A polynomial-time algorithm, based on Newton's method, for linear programming
• A simple, combinatorial algorithm for solving SDD systems in nearly-linear time
• Almost universally optimal distributed Laplacian solvers via low-congestion shortcuts
• An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem
• An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations
• An efficient parallel solver for SDD linear systems
• Approaching optimality for solving SDD linear systems
• Approximate undirected maximum flows in \(O(m\operatorname{polylog}(n))\) time
• Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
• Distributed Computing: A Locality-Sensitive Approach
• Distributed algorithms for planar networks. II: Low-congestion shortcuts, MST, and Min-Cut
• Distributed approximate maximum matching in the CONGEST model
• Distributed verification and hardness of distributed approximation
• Extensions of Lipschitz mappings into a Hilbert space
• Fast approximation of matrix coherence and statistical leverage
• Faster energy maximization for faster maximum flow
• Faster parallel algorithm for approximate shortest path
• Graph sparsification by effective resistances
• Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
• Near-optimal distributed maximum flow
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• Negative-weight shortest paths and unit capacity minimum cost flow in \(\tilde{O}(m^{10/7}\log W)\) time (extended abstract)
• Parallel approximate undirected shortest paths via low hop emulators
• Randomized Algorithms for Matrices and Data
• Single-source shortest paths in the CONGEST model with improved bounds
• Sketching as a tool for numerical linear algebra
• Solving SDD linear systems in nearly \(m \log^{1/2} n\) time
• Sparsified Cholesky and multigrid solvers for connection Laplacians
• Uniform sampling for matrix approximation

This page was built for publication: Minimum cost flow in the CONGEST model

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