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