Minimum cost flow in the CONGEST model

DOI10.1007/978-3-031-32733-9_18arXiv2304.01600OpenAlexW4377971925MaRDI QIDQ6148076FDOQ6148076

Authors: Tijn de Vos 

Publication date: 11 January 2024

Published in: Structural Information and Communication Complexity (Search for Journal in Brave)

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.

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)

Cites Work

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

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)