Distributed Verification and Hardness of Distributed Approximation
From MaRDI portal
Publication:4907581
DOI10.1137/11085178XzbMath1259.68227OpenAlexW2083323175MaRDI QIDQ4907581
Atish Das Sarma, Amos Korman, Stephan Holzer, Liah Kor, Gopal Pandurangan, Roger Wattenhofer, Danupon Nanongkai, David Peleg
Publication date: 4 February 2013
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/11085178x
lower boundsdistributed algorithmscommunication complexityhardness of approximationgraph optimization problems
Network design and communication in computer systems (68M10) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)
Related Items (50)
Latency, capacity, and distributed minimum spanning trees ⋮ Sublinear-time distributed algorithms for detecting small cliques and even cycles ⋮ Fast Distributed Approximation for TAP and 2-Edge-Connectivity ⋮ Proof-labeling schemes: broadcast, unicast and in between ⋮ Distributed Testing of Distance-k Colorings ⋮ Local checkability, no strings attached: (a)cyclicity, reachability, loop free updates in SDNs ⋮ Communication costs in a geometric communication network ⋮ Unnamed Item ⋮ What can be sampled locally? ⋮ Routing schemes for hybrid communication networks ⋮ Minimum cost flow in the CONGEST model ⋮ Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions ⋮ A distributed algorithm for directed minimum-weight spanning tree ⋮ (1- ϵ )-Approximate Maximum Weighted Matching in poly(1/ ϵ , log n ) Time in the Distributed and Parallel Settings ⋮ Brief Announcement: Minimum Cost Maximum Flow in the CONGEST Model ⋮ Asynchronous Wait-Free Runtime Verification and Enforcement of Linearizability ⋮ The sparsest additive spanner via multiple weighted BFS trees ⋮ Unnamed Item ⋮ Locality and checkability in wait-free computing ⋮ A hierarchy of local decision ⋮ Distributed Graph Algorithms and their Complexity: An Introduction ⋮ Detecting cliques in CONGEST networks ⋮ Fooling views: a new lower bound technique for distributed computations under congestion ⋮ Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model ⋮ Fast and compact self-stabilizing verification, computation, and fault detection of an MST ⋮ On efficient distributed construction of near optimal routing schemes ⋮ Fast distributed approximation for TAP and 2-edge-connectivity ⋮ On mobile agent verifiable problems ⋮ Randomized proof-labeling schemes ⋮ Randomized distributed decision ⋮ Distributed construction of purely additive spanners ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Redundancy in distributed proofs ⋮ Fast distributed algorithms for testing graph properties ⋮ Approximate proof-labeling schemes ⋮ Compact distributed certification of planar graphs ⋮ Message lower bounds via efficient network synchronization ⋮ Distributed Approximate Maximum Matching in the CONGEST Model. ⋮ The Sparsest Additive Spanner via Multiple Weighted BFS Trees ⋮ Message Lower Bounds via Efficient Network Synchronization ⋮ Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models ⋮ A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths ⋮ Distributed Spanner Approximation ⋮ Local certification of graphs with bounded genus ⋮ Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time ⋮ A distributed enumeration algorithm and applications to all pairs shortest paths, diameter\dots ⋮ Approximate minimum directed spanning trees under congestion
This page was built for publication: Distributed Verification and Hardness of Distributed Approximation
