Brief Announcement: The Laplacian Paradigm in Deterministic Congested Clique

DOI10.1145/3583668.3594577MaRDI QIDQ6202226zbMATH OpenOpenAlexFDO

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)

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)

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.

Cites work

• A Nearly-m log n Time Solver for SDD Linear Systems
• A simple, combinatorial algorithm for solving SDD systems in nearly-linear time
• 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 Max-Flow on Small Depth Networks
• Approximate undirected maximum flows in \(O(m\operatorname{polylog}(n))\) time
• Deterministic coin tossing with applications to optimal parallel list ranking
• Distributed algorithms for planar networks. II: Low-congestion shortcuts, MST, and Min-Cut
• Faster energy maximization for faster maximum flow
• Faster parallel algorithm for approximate shortest path
• Maximal Flow Through a Network
• Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
• 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
• Optimal deterministic routing and sorting on the congested clique
• Parallel approximate undirected shortest paths via low hop emulators
• Solving SDD linear systems in nearly \(m \log^{1/2} n\) time
• Sparsified Cholesky and multigrid solvers for connection Laplacians

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)