Local computation: lower and upper bounds
From MaRDI portal
approximation hardnessbutterfly effectdistributed algorithmsdominating setlocalitylower boundsmaximal independent setmaximal matchingpolylog-localvertex cover
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed algorithms (68W15) Approximation algorithms (68W25) Combinatorial optimization (90C27)
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.
Recommendations
Cited in
(75)- Linear-in- lower bounds in the LOCAL model
- Computing large independent sets in a single round
- Input locality and hardness amplification
- Local planar domination revisited
- Linial for lists
- Constant round distributed domination on graph classes with bounded expansion
- Distributed distance domination in graphs with no \(K_{2,t}\)-minor
- Distributed reconfiguration of maximal independent sets
- What can be sampled locally?
- Derandomizing local distributed algorithms under bandwidth restrictions
- Fooling views: a new lower bound technique for distributed computations under congestion
- Combinatorial algorithms for distributed graph coloring
- No sublogarithmic-time approximation scheme for bipartite vertex cover
- Distributed coloring algorithms for triangle-free graphs
- Can we locally compute sparse connected subgraphs?
- Optimal distributed covering algorithms
- Constant-Time Local Computation Algorithms
- Survey of local algorithms
- Constant space and non-constant time in distributed computing
- Leveraging Linial’s Locality Limit
- Distributed minimum dominating set approximations in restricted families of graphs
- Local Computation Schemes with Partially Ordered Preferences
- An exponential separation between randomized and deterministic complexity in the LOCAL model
- A time hierarchy theorem for the LOCAL model
- scientific article; zbMATH DE number 1837654 (Why is no real title available?)
- What Can be Computed Locally?
- Distributed Dominating Set Approximations beyond Planar Graphs
- Distributed spanner approximation
- \((\Delta+1)\) coloring in the congested clique model
- Fast Distributed Approximation for Max-Cut
- Distributed approximate maximum matching in the CONGEST model
- Distributed set cover approximation: primal-dual with optimal locality
- Derandomizing distributed algorithms with small messages: spanners and dominating set
- Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds
- Distributed Reconfiguration of Maximal Independent Sets
- Distributed (+1)-coloring via ultrafast graph shattering
- On the locality of bounded growth
- Veracity radius, capturing the locality of distributed computations
- Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring
- What cannot be computed locally!
- Logical locality entails frugal distributed computation over graphs (extended abstract)
- Distributed Lower Bounds for Ruling Sets
- Distributed distance-r covering problems on sparse high-girth graphs
- Simple and local independent set approximation
- A topological perspective on distributed network algorithms
- Distributed algorithms for the Lovász local lemma and graph coloring
- Distributed distance-\(r\) covering problems on sparse high-girth graphs
- Node and edge averaged complexities of local graph problems
- Local MST computation with short advice
- Exact distributed sampling
- Distributed dominating sets in interval graphs
- The energy complexity of diameter and minimum cut computation in bounded-genus networks
- The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs
- (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
- Local conflict coloring revisited: Linial for lists
- Improved MPC algorithms for MIS, matching, and coloring on trees and beyond
- Distributed maximum matching verification in CONGEST
- Distributed domination on sparse graph classes
- Near-optimal distributed dominating set in bounded arboricity graphs
- Sample-and-gather: fast ruling set algorithms in the low-memory MPC model
- Exponential speedup over locality in \textsf{MPC} with optimal memory
- The message complexity of distributed graph optimization
- Mobile agents on chordal graphs: maximum independent set and beyond
- Rounds vs. communication tradeoffs for maximal independent sets
- Brief announcement: Massively parallel ruling set made deterministic
- Distributed fractional local ratio and independent set approximation
- Distributed independent sets in interval and segment intersection graphs
- Distributed MIS in O( n) awake complexity
- A simple distributed algorithm for sparse fractional covering and packing problems
- Query efficient weighted stochastic matching
- Distributed independent sets in interval and segment intersection graphs
- Deterministic local algorithms, unique identifiers, and fractional graph colouring
- An interpretation of Shenoy and Shafer's axioms for local computation
This page was built for publication: Local computation: lower and upper bounds
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3177774)
