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