Local Computation
From MaRDI portal
Publication:3177774
DOI10.1145/2742012zbMATH Open1426.68092arXiv1011.5470OpenAlexW1957963525MaRDI QIDQ3177774FDOQ3177774
Roger Wattenhofer, Fabian Kuhn, Thomas Moscibroda
Publication date: 2 August 2018
Published in: Journal of the ACM (Search for Journal in Brave)
Abstract: The question of what can be computed, and how efficiently, are at the core of computer science. Not surprisingly, in distributed systems and networking research, an equally fundamental question is what can be computed in a emph{distributed} fashion. More precisely, if nodes of a network must base their decision on information in their local neighborhood only, how well can they compute or approximate a global (optimization) problem? In this paper we give the first poly-logarithmic lower bound on such local computation for (optimization) problems including minimum vertex cover, minimum (connected) dominating set, maximum matching, maximal independent set, and maximal matching. In addition we present a new distributed algorithm for solving general covering and packing linear programs. For some problems this algorithm is tight with the lower bounds, for others it is a distributed approximation scheme. Together, our lower and upper bounds establish the local computability and approximability of a large class of problems, characterizing how much local information is required to solve these tasks.
Full work available at URL: https://arxiv.org/abs/1011.5470
lower boundsdistributed algorithmsdominating setmaximal independent setvertex coverlocalityapproximation hardnessmaximal matchingbutterfly effectpolylog-local
Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distributed algorithms (68W15)
Cited In (58)
- Distributed domination on sparse graph classes
- (1- ϵ )-Approximate Maximum Weighted Matching in poly(1/ ϵ , log n ) Time in the Distributed and Parallel Settings
- Distributed MIS in O(log log n) Awake Complexity
- Distributed MIS with Low Energy and Time Complexities
- The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs
- Near-optimal distributed dominating set in bounded arboricity graphs
- Distributed maximum matching verification in CONGEST
- Local conflict coloring revisited: Linial for lists
- Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set
- Fast Distributed Approximation for Max-Cut
- A topological perspective on distributed network algorithms
- Linial for lists
- Distributed independent sets in interval and segment intersection graphs
- Combinatorial algorithms for distributed graph coloring
- Local Computation Schemes with Partially Ordered Preferences
- Distributed distance-\(r\) covering problems on sparse high-girth graphs
- Dynamic networks of finite state machines
- Fooling views: a new lower bound technique for distributed computations under congestion
- Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering
- Local MST computation with short advice
- Exact distributed sampling
- Derandomizing local distributed algorithms under bandwidth restrictions
- Distributed set cover approximation: Primal-dual with optimal locality
- Constant space and non-constant time in distributed computing
- (Delta+1) Coloring in the Congested Clique Model
- Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds
- Constant-Time Local Computation Algorithms
- Distributed algorithms for the Lovász local lemma and graph coloring
- What Can be Computed Locally?
- Distributed dominating sets in interval graphs
- A Time Hierarchy Theorem for the LOCAL Model
- Distributed distance domination in graphs with no \(K_{2,t}\)-minor
- No sublogarithmic-time approximation scheme for bipartite vertex cover
- An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model
- Distributed Approximate Maximum Matching in the CONGEST Model.
- Simple and local independent set approximation
- The energy complexity of diameter and minimum cut computation in bounded-genus networks
- Deterministic local algorithms, unique identifiers, and fractional graph colouring
- Distributed distance-\(r\) covering problems on sparse high-girth graphs
- Distributed Dominating Set Approximations beyond Planar Graphs
- An interpretation of Shenoy and Shafer's axioms for local computation
- Distributed Lower Bounds for Ruling Sets
- Linear-in-\(\varDelta \) lower bounds in the LOCAL model
- Distributed minimum dominating set approximations in restricted families of graphs
- Distributed reconfiguration of maximal independent sets
- Optimal distributed covering algorithms
- Title not available (Why is that?)
- Input locality and hardness amplification
- What can be sampled locally?
- Node and edge averaged complexities of local graph problems
- Improved MPC algorithms for MIS, matching, and coloring on trees and beyond
- Distributed coloring algorithms for triangle-free graphs
- Computing large independent sets in a single round
- Distributed Spanner Approximation
- Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring
- Distributed Reconfiguration of Maximal Independent Sets
- Local planar domination revisited
- Constant round distributed domination on graph classes with bounded expansion
This page was built for publication: Local Computation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3177774)
