Viewing the Rings of a Tree: Minimum Distortion Embeddings into Trees

Date

2019-01

ORCID

Journal Title

Journal ISSN

Volume Title

Publisher

Association for Computing Machinery

item.page.doi

Abstract

We describe a (1 + ε) approximation algorithm for finding the minimum distortion embedding of an npoint metric space, (X, d_X), into a tree with vertex set X. The running time of our algorithm is n²•(∆/ε)^{(O(δopt/ε))2λ+1} parameterized with respect to the spread of X, denoted by ∆, the minimum possible distortion for embedding X into any tree, denoted by δ_{opt}, and the doubling dimension of X, denoted by λ. Hence we obtain a PTAS, provided δ_{opt} is a constant and X is a finite doubling metric space with polynomially bounded spread, for example, a point set with polynomially bounded spread in constant dimensional Euclidean space. Our algorithm implies a constant factor approximation with the same running time when Steiner vertices are allowed. Moreover, we describe a similar (1 + ε) approximation algorithm for finding a tree spanner of (X, d_X) that minimizes the maximum stretch. The running time of our algorithm stays the same, except that δoptmust be interpreted as the minimum stretch of any spanning tree of X. Finally, we generalize our tree spanner algorithm to a (1 + ε) approximation algorithm for computing a minimum stretch tree spanner of a weighted graph, where the running time is parameterized with respect to the maximum degree, in addition to the other parameters above. In particular, we obtain a PTAS for computing minimum stretch tree spanners of weighted graphs, with polynomially bounded spread, constant doubling dimension, and constant maximum degree, when a tree spanner with constant stretch exists. Copyright © 2019 by SIAM.

Description

Due to copyright restrictions and/or publisher's policy full text access from Treasures at UT Dallas is limited to current UTD affiliates (use the provided Link to Article).

Keywords

Approximation algorithms, Embeddings (Mathematics), Geometry, Graph theory, Graphic methods, Parameter estimation, Set theory

item.page.sponsorship

NSF CRII Award (1566624 and 1566137) and CAREER award 1750780

Rights

©2019 SIAM

Citation