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

centralized local algorithmsdistributed local algorithmsgraph algorithmsmaximum matchingmaximum weighted matchingsublinear approximation algorithms

Mathematics Subject Classification ID

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

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

• A Local Computation Approximation Scheme to Maximum Matching
• A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• 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 \((\Delta+1)\)-coloring in linear (in \(\Delta\)) time
• Distributed \((\Delta+1)\)-coloring in sublogarithmic rounds
• Distributed Computing: A Locality-Sensitive Approach
• Fast Distributed Approximations in Planar Graphs
• Fast primal-dual distributed algorithms for scheduling and matching problems
• scientific article; zbMATH DE number 7075933 (Why is no real title available?)
• Improved constant-time approximation algorithms for maximum matchings and other optimization problems
• Improved Distributed Approximate Matching
• 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

(10)

• 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?
• Deterministic stateless centralized local algorithms for bounded degree graphs
• Adapting local sequential algorithms to the distributed setting
• Average Sensitivity of Graph Algorithms
• Distributed computing in the asynchronous LOCAL model
• Spanning adjacency oracles in sublinear time
• Nearly optimal local algorithms for constructing sparse spanners of clusterable graphs
• Narrowing the \textsf{LOCAL-CONGEST} gaps in sparse networks via expander decompositions

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)