Parallel metric tree embedding based on an algebraic view on Moore-Bellman-Ford

DOI10.1145/3231591zbMATH Open1426.68211arXiv1509.09047OpenAlexW2902652525WikidataQ128878342 ScholiaQ128878342MaRDI QIDQ4625664FDOQ4625664

Authors: Stephan Friedrichs, Christoph Lenzen 

Publication date: 25 February 2019

Published in: Journal of the ACM (Search for Journal in Brave)

Abstract: A emph{metric tree embedding} of expected emph{stretch~$alphageq1$} maps a weighted $n$-node graph $G=(V,E,omega)$ to a weighted tree $T=(V_T,E_T,omeg{a}_T)$ with $Vsubseteq{V}_T$ such that, for all $v,winV$, $operatornamedist(v,w,G)leqoperatornamedist(v,w,T)$ and $operatornameE[operatornamedist(v,w,T)]leqalphaoperatornamedist(v,w,G)$. Such embeddings are highly useful for designing fast approximation algorithms, as many hard problems are easy to solve on tree instances. However, to date the best parallel $(operatornamepolylogn)$-depth algorithm that achieves an asymptotically optimal expected stretch of $alphainoperatornameO(logn)$ requires $operatornameOmega(n^2)$ work and a metric as input. In this paper, we show how to achieve the same guarantees using $operatornamepolylogn$ depth and $operatornameildeO(m^{1+epsilon})$ work, where $m=|E|$ and $epsilon>0$ is an arbitrarily small constant. Moreover, one may further reduce the work to $operatornameildeO(m+n^{1+epsilon})$ at the expense of increasing the expected stretch to $operatornameO(epsilo{n}^{-1}logn)$. Our main tool in deriving these parallel algorithms is an algebraic characterization of a generalization of the classic Moore-Bellman-Ford algorithm. We consider this framework, which subsumes a variety of previous "Moore-Bellman-Ford-like" algorithms, to be of independent interest and discuss it in depth. In our tree embedding algorithm, we leverage it for providing efficient query access to an approximate metric that allows sampling the tree using $operatornamepolylogn$ depth and $operatornameildeO(m)$ work. We illustrate the generality and versatility of our techniques by various examples and a number of additional results.

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

Recommendations

• scientific article; zbMATH DE number 7204478
• Approximation algorithms for embedding general metrics into trees
• A tight bound on approximating arbitrary metrics by tree metrics
• A tight bound on approximating arbitrary metrics by tree metrics
• Multiembedding of Metric Spaces

zbMATH Keywords

PRAM\(k\)-medianbuy-at-bulk network designapproximate metrichop setsMBF-like algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Network design and communication in computer systems (68M10)

Cited In (5)

• Lasserre integrality gaps for graph spanners and related problems
• Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions
• Single-source shortest paths in the CONGEST model with improved bounds
• Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC
• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths

This page was built for publication: Parallel metric tree embedding based on an algebraic view on Moore-Bellman-Ford

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4625664)