Exponentially Faster Shortest Paths in the Congested Clique
METADATA ONLY
Loading...
Author / Producer
Date
2022-08
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
We present improved deterministic algorithms for approximating shortest paths in the Congested Clique model of distributed computing. We obtain poly(log log n)-round algorithms for the following problems in unweighted undirected n-vertex graphs:
( 1 + ϵ)-approximation of multi-source shortest paths (MSSP) from O(√ n) sources.
(2 + ϵ)-approximation of all pairs shortest paths (APSP).
(1 + ϵ, β)-approximation of APSP where β = O (log log n/ϵ)log log n.
These bounds improve exponentially over the state-of-the-art poly-logarithmic bounds due to [Censor-Hillel et al., PODC19]. It also provides the first nearly-additive bounds for the APSP problem in sub-polynomial time. Our approach is based on distinguishing between short and long distances based on some distance threshold t = O(β/ϵ) where β = O (log log n/ϵ)log log n. Handling the long distances is done by devising a new algorithm for computing a sparse (1 + ϵ, β) emulator with O (n log log n) edges. For the short distances, we provide distance-sensitive variants for the distance tool-kit of [Censor-Hillel et al., PODC19]. By exploiting the fact that this tool-kit should be applied only on local balls of radius t, their round complexities get improved from poly (log n) to poly (log t).
Finally, our deterministic solutions for these problems are based on a derandomization scheme of a novel variant of the hitting set problem, which might be of independent interest.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
69 (4)
Pages / Article No.
29
Publisher
Association for Computing Machinery
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Shortest paths; congested clique; near-additive emulator