Improved All-Pairs Approximate Shortest Paths in Congested Clique
<|reference_start|>Improved All-Pairs Approximate Shortest Paths in Congested Clique: In this paper, we present new algorithms for approximating All-Pairs Shortest Paths (APSP) in the Congested Clique model. We present randomized algorithms for weighted undirected graphs.   Our first contribution is an $O(1)$-approximate APSP algorithm taking just $O(\log \log \log n)$ rounds. Prior to our work, the fastest algorithms that give an $O(1)$-approximation for APSP take $\operatorname{poly}(\log{n})$ rounds in weighted undirected graphs, and $\operatorname{poly}(\log \log n)$ rounds in unweighted undirected graphs.   If we terminate the execution of the algorithm early, we obtain an $O(t)$-round algorithm that yields an $O \big( (\log n)^{1/2^t} \big) $ distance approximation for a parameter $t$. The trade-off between $t$ and the approximation quality provides flexibility for different scenarios, allowing the algorithm to adapt to specific requirements. In particular, we can get an $O \big( (\log n)^{1/2^t} \big) $-approximation for any constant $t$ in $O(1)$-rounds. Such result was previously known only for the special case that $t=0$.   A key ingredient in our algorithm is a lemma that allows to improve an $O(a)$-approximation for APSP to an $O(\sqrt{a})$-approximation for APSP in $O(1)$ rounds. To prove the lemma, we develop several new tools, including $O(1)$-round algorithms for computing the $k$ closest nodes, a certain type of hopset, and skeleton graphs.<|reference_end|>
@article{bui2024improved,
    title={Improved All-Pairs Approximate Shortest Paths in Congested Clique},
    author={Hong Duc Bui and Shashwat Chandra and Yi-Jun Chang and Michal Dory and
  Dean Leitersdorf},
    journal={arXiv preprint arXiv:2405.02695},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.02695},
    primaryClass={cs.DS cs.DC}
}