Best of two local models: centralized local and distributed local algorithms

DOI10.1016/J.IC.2018.07.001MaRDI QIDQ1784947zbMATH OpenOpenAlexFDO

Authors Guy Even, Moti Medina, Dana Ron

Publication date 27 September 2018

Published in Information and Computation (Search for Journal in Brave)

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

zbMATH Keywords

graph algorithmsmaximum matchingmaximum weighted matchingsublinear approximation algorithmscentralized local algorithmsdistributed local algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distributed algorithms (68W15)

Abstract: We consider two models of computation: centralized local algorithms and local distributed algorithms. Algorithms in one model are adapted to the other model to obtain improved algorithms. Distributed vertex coloring is employed to design improved centralized local algorithms for: maximal independent set, maximal matching, and an approximation scheme for maximum (weighted) matching over bounded degree graphs. The improvement is threefold: the algorithms are deterministic, stateless, and the number of probes grows polynomially in $lo{g}^{\ast }n$, where $n$ is the number of vertices of the input graph. The recursive centralized local improvement technique by Nguyen and Onak~cite{onak2008} is employed to obtain an improved distributed approximation scheme for maximum (weighted) matching. The improvement is twofold: we reduce the number of rounds from $O(logn)$ to $O(lo{g}^{\ast }n)$ for a wide range of instances and, our algorithms are deterministic rather than randomized.

Recommendations

• Deterministic stateless centralized local algorithms for bounded degree graphs
• Distributed local approximation algorithms for maximum matching in graphs and hypergraphs
• Distributed approximation of maximum independent set and maximum matching
• Improved Distributed Approximate Matching
• Improved deterministic distributed matching via rounding

Cites work

• scientific article; zbMATH DE number 7075933 (Why is no real title available?)
• A Local Computation Approximation Scheme to Maximum Matching
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
• A simpler linear time \( \frac{2}{3} - \varepsilon\) approximation for maximum weight matching
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
• Approximating weighted matchings in parallel
• Converting online algorithms to local computation algorithms
• Deterministic coin tossing with applications to optimal parallel list ranking
• Deterministic stateless centralized local algorithms for bounded degree graphs
• Distributed Computing: A Locality-Sensitive Approach
• Distributed \((\Delta+1)\)-coloring in linear (in \(\Delta\)) time
• Distributed \((\Delta+1)\)-coloring in sublogarithmic rounds
• Fast Distributed Approximations in Planar Graphs
• Fast primal-dual distributed algorithms for scheduling and matching problems
• Improved Distributed Approximate Matching
• Improved constant-time approximation algorithms for maximum matchings and other optimization problems
• Leveraging Linial’s Locality Limit
• Local computation algorithms for graphs of non-constant degrees
• Locality in Distributed Graph Algorithms
• New techniques and tighter bounds for local computation algorithms
• Non-local probes do not help with many graph problems
• Parallel Symmetry-Breaking in Sparse Graphs
• Some simple distributed algorithms for sparse networks
• Space-efficient local computation algorithms
• Survey of local algorithms

Cited in

(7)

• Non-local probes do not help with many graph problems
• Distributed computing in the asynchronous LOCAL model
• Can we locally compute sparse connected subgraphs?
• Deterministic stateless centralized local algorithms for bounded degree graphs
• Adapting local sequential algorithms to the distributed setting
• Local models-an approach to distributed multi-objective optimization
• Average Sensitivity of Graph Algorithms

This page was built for publication: Best of two local models: centralized local and distributed local algorithms

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