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

This paper makes two main contributions: a construction of a near-minimum spanning tree with constant average distortion, and a general equivalence theorem relating two refined notions of distortion: scaling distortion and prioritized distortion. Scaling distortion provides improved distortion for 1...

Full description

Saved in:
Bibliographic Details
Published in:Journal of computer and system sciences 2019-11, Vol.105, p.116-129
Main Authors: Bartal, Yair, Filtser, Arnold, Neiman, Ofer
Format: Article
Language:English
Subjects:
Average distortion
Light spanner
Metric embedding
Prioritized distortion
Scaling distortion
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper makes two main contributions: a construction of a near-minimum spanning tree with constant average distortion, and a general equivalence theorem relating two refined notions of distortion: scaling distortion and prioritized distortion. Scaling distortion provides improved distortion for 1−ϵ fractions of the pairs, for all ϵ simultaneously. A stronger version called coarse scaling distortion, has improved distortion guarantees for the furthest pairs. Prioritized distortion allows 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. This equivalence is used to construct the near-minimum spanning tree with constant average distortion, and has many further implications to metric embeddings theory. Among other results, we obtain a strengthening of Bourgain's theorem on embedding arbitrary metrics into Euclidean space, possessing optimal prioritized distortion.
ISSN:0022-0000
1090-2724
DOI:10.1016/j.jcss.2019.04.006