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

DOI10.1016/J.IC.2018.07.001zbMATH Open1401.68356arXiv1402.3796OpenAlexW2886624408MaRDI QIDQ1784947FDOQ1784947

Authors: Guy Even, Moti Medina, Dana Ron 

Publication date: 27 September 2018

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

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.

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

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

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)

Cites Work

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

Cited In (7)

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

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)