On notions of distortion and an almost minimum spanning tree with constant average distortion

DOI10.1016/J.JCSS.2019.04.006MaRDI QIDQ2316932zbMATH OpenOpenAlexWikidataFDO

Authors Arnold Filtser, Ofer Neiman, Yair Bartal

Publication date 7 August 2019

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

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

zbMATH Keywords

average distortionlight spannermetric embeddingprioritized distortionscaling distortion

Mathematics Subject Classification ID

Distance in graphs (05C12) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Abstract: This paper makes two main contributions: The first is the construction of a near-minimum spanning tree with constant average distortion. The second is a general equivalence theorem relating two refined notions of distortion: scaling distortion and prioritized distortion. Minimum Spanning Trees of weighted graphs are fundamental objects in numerous applications. In particular in distributed networks, the minimum spanning tree of the network is often used to route messages between network nodes. Unfortunately, while being most efficient in the total cost of connecting all nodes, minimum spanning trees fail miserably in the desired property of approximately preserving distances between pairs. While known lower bounds exclude the possibility of the worst case distortion of a tree being small, it was shown in [ABN15] that there exists a spanning tree with constant average distortion. Yet, the weight of such a tree may be significantly larger than that of the MST. In this paper, we show that any weighted undirected graph admits a {em spanning tree} whose weight is at most $(1+ho)$ times that of the MST, providing {em constant average distortion} $O(1/ho)$. Our result exhibits the best possible tradeoff of this type. This result makes use of a general equivalence theorem relating two recently developed notions of distortion for metric embedding. The first is the notion of scaling distortion, which provides improved distortion for $1-epsilon$ fractions of the pairs, for all $epsilon$ simultaneously. A stronger version called coarse scaling distortion, has improved distortion guarantees for the furthest pairs. The second notion is that of prioritized distortion, a property allowing to prioritize the nodes whose associated distortions will be improved. We show that prioritized distortion is essentially equivalent to coarse scaling distortion via a general transformation.

Recommendations

• On notions of distortion and an almost minimum spanning tree with constant average distortion
• Embedding metrics into ultrametrics and graphs into spanning trees with constant average distortion
• Embedding metrics into ultrametrics and graphs into spanning trees with constant average distortion
• Approximation algorithms for minimizing average distortion
• Viewing the rings of a tree: minimum distortion embeddings into trees

Cites work

• A Graph-Theoretic Game and Its Application to the k-Server Problem
• A tight bound on approximating arbitrary metrics by tree metrics
• Advances in metric embedding theory
• Algorithms – ESA 2004
• Approximate distance oracles with improved bounds
• Constructing Light Spanners Deterministically in Near-Linear Time
• Embedding metrics into ultrametrics and graphs into spanning trees with constant average distortion
• scientific article; zbMATH DE number 437549 (Why is no real title available?)
• scientific article; zbMATH DE number 1775400 (Why is no real title available?)
• Light spanners
• Lower-Stretch Spanning Trees
• Near-optimal light spanners
• NEW SPARSENESS RESULTS ON GRAPH SPANNERS
• On Lipschitz embedding of finite metric spaces in Hilbert space
• On notions of distortion and an almost minimum spanning tree with constant average distortion
• Spanners with Slack
• Steiner Minimal Trees
• Terminal embeddings
• The greedy spanner is existentially optimal (extended abstract)
• Triangulation and embedding using small sets of beacons
• Using petal-decompositions to build a low stretch spanning tree
• Volume in general metric spaces

Cited in

(15)

• Constructing light spanners deterministically in near-linear time
• Embedding metrics into ultrametrics and graphs into spanning trees with constant average distortion
• On notions of distortion and an almost minimum spanning tree with constant average distortion
• The greedy spanner is existentially optimal
• Constructing Light Spanners Deterministically in Near-Linear Time
• Lossless prioritized embeddings
• Embedding metrics into ultrametrics and graphs into spanning trees with constant average distortion
• Labelings vs. embeddings: on distributed and prioritized representations of distances
• Scattering and sparse partitions, and their applications
• Light, reliable spanners
• Lightweight near-additive spanners
• A face cover perspective to _1 embeddings of planar graphs
• Scattering and sparse partitions, and their applications
• On sparse covers of minor free graphs, low dimensional metric embeddings, and other applications
• Light reliable spanners

This page was built for publication: On notions of distortion and an almost minimum spanning tree with constant average distortion

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