Distributed verification and hardness of distributed approximation

DOI10.1145/1993636.1993686zbMath1288.68110arXiv1011.3049OpenAlexW2030825457MaRDI QIDQ5419106

Danupon Nanongkai, Roger Wattenhofer, Stephan Holzer, Liah Kor, Atish Das Sarma, Amos Korman, Gopal Pandurangan, David Peleg

Publication date: 5 June 2014

Published in: Proceedings of the forty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

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

zbMATH Keywords

shortest pathlower boundgraph algorithmstime complexityminimum spanning treedistributed algorithmscommunication complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Distributed algorithms (68W15)

Related Items (21)

Tight bounds for parallel randomized load balancing ⋮ Distributed Broadcast Revisited: Towards Universal Optimality ⋮ The Cost of Fault Tolerance in Multi-Party Communication Complexity ⋮ Single-source shortest paths in the CONGEST model with improved bounds ⋮ Low-congestion shortcuts without embedding ⋮ Some lower bounds in dynamic networks with oblivious adversaries ⋮ Tight bounds for distributed minimum-weight spanning tree verification ⋮ Communication costs in a geometric communication network ⋮ Almost universally optimal distributed Laplacian solvers via low-congestion shortcuts ⋮ Distributed distance computation and routing with small messages ⋮ Low-congestion shortcut and graph parameters ⋮ Deciding and verifying network properties locally with few output bits ⋮ Algebraic methods in the congested clique ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Efficient distributed approximation algorithms via probabilistic tree embeddings ⋮ Locality and Checkability in Wait-Free Computing ⋮ Sparsifying Congested Cliques and Core-Periphery Networks ⋮ Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree ⋮ Unnamed Item ⋮ Near-Optimal Distributed Maximum Flow

This page was built for publication: Distributed verification and hardness of distributed approximation