Brief Announcement: The Laplacian Paradigm in Deterministic Congested Clique

DOI10.1145/3583668.3594577arXiv2304.02315OpenAlexW4380880046MaRDI QIDQ6202226FDOQ6202226

Authors: Sebastian Forster, Tijn de Vos 

Publication date: 26 March 2024

Published in: Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Abstract: In this paper, we bring the techniques of the Laplacian paradigm to the congested clique, while further restricting ourselves to deterministic algorithms. In particular, we show how to solve a Laplacian system up to precision $epsilon$ in $n^{o(1)}log(1/epsilon)$ rounds. We show how to leverage this result within existing interior point methods for solving flow problems. We obtain an $m^{3/7+o(1)}{U}^{1/7}$ round algorithm for maximum flow on a weighted directed graph with maximum weight $U$, and we obtain an $ildeO(m^{3/7}(n^{0.158}+n^{o(1)}extpolylogW))$ round algorithm for unit capacity minimum cost flow on a directed graph with maximum cost $W$. Hereto, we give a novel routine for computing Eulerian orientations in $O(lognlo{g}^{\ast }n)$ rounds, which we believe may be of separate interest.

Full work available at URL: https://arxiv.org/abs/2304.02315

zbMATH Keywords

maximum flowminimum cost flowcongested cliqueLaplacian solverspectral sparsifier

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

Cites Work

• Maximal Flow Through a Network
• 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
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• Optimal deterministic routing and sorting on the congested clique
• Deterministic coin tossing with applications to optimal parallel list ranking
• Approximate Max-Flow on Small Depth Networks
• Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
• Sparsified Cholesky and multigrid solvers for connection Laplacians
• Algebraic methods in the congested clique
• 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
• 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
• Near-optimal distributed maximum flow
• Approximate undirected maximum flows in \(O(m\operatorname{polylog}(n))\) time

This page was built for publication: Brief Announcement: The Laplacian Paradigm in Deterministic Congested Clique

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