Lower bounds for local approximation

DOI10.1145/2332432.2332465zbMath1301.68147arXiv1201.6675OpenAlexW2135290452MaRDI QIDQ2933794

Jukka Suomela, Mika Göös, Juho Hirvonen

Publication date: 5 December 2014

Published in: Journal of the ACM, Proceedings of the 2012 ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1201.6675

zbMATH Keywords

approximation algorithmslocal algorithmsedge dominating setunique identifiersdeterministic distributed algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Distributed algorithms (68W15)

Related Items (17)

Node labels in local decision ⋮ Constant space and non-constant time in distributed computing ⋮ Linear-in-\(\varDelta \) lower bounds in the LOCAL model ⋮ Deterministic local algorithms, unique identifiers, and fractional graph colouring ⋮ Distributed half-integral matching and beyond ⋮ Distributed half-integral matching and beyond ⋮ The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs ⋮ Distributed \(\mathcal{CONGEST}_{B C}\) constant approximation of MDS in bounded genus graphs ⋮ A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs ⋮ Distributed Graph Algorithms and their Complexity: An Introduction ⋮ Improved distributed local approximation algorithm for minimum 2-dominating set in planar graphs ⋮ Constant-time local computation algorithms ⋮ No sublogarithmic-time approximation scheme for bipartite vertex cover ⋮ Local approximation of the maximum cut in regular graphs ⋮ Fast and Simple Local Algorithms for 2-Edge Dominating Sets and 3-Total Vertex Covers ⋮ Weak models of distributed computing, with connections to modal logic ⋮ A local approximation algorithm for minimum dominating set problem in anonymous planar networks

This page was built for publication: Lower bounds for local approximation