Bypassing the embedding
- 13 June 2004
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 281-290
- https://doi.org/10.1145/1007352.1007399
Abstract
The doubling dimension of a metric is the smallest k such that any ball of radius 2r can be covered using 2k balls of radius r. This concept for abstract metrics has been proposed as a natural analog to the dimension of a Euclidean space. If we could embed metrics with low doubling dimension into low dimensional Euclidean spaces, they would inherit several algorithmic and structural properties of the Euclidean spaces. Unfortunately however, such a restriction on dimension does not suffice to guarantee embeddibility in a normed space.In this paper we explore the option of bypassing the embedding. In particular we show the following for low dimensional metrics: Quasi-polynomial time (1+ε)-approximation algorithm for various optimization problems such as TSP, k-median and facility location. (1+ε)-approximate distance labeling scheme with optimal label length. (1+ε)-stretch polylogarithmic storage routing scheme.Keywords
This publication has 29 references indexed in Scilit:
- Compact and localized distributed data structuresDistributed Computing, 2003
- PLANE WITH $A_{\infty}$ -WEIGHTED METRIC NOT BILIPSCHITZ EMBEDDABLE TO ${\bb R}^n$Bulletin of the London Mathematical Society, 2002
- Compact Routing with Minimum StretchJournal of Algorithms, 2001
- A Global Geometric Framework for Nonlinear Dimensionality ReductionScience, 2000
- Min-Wise Independent PermutationsJournal of Computer and System Sciences, 2000
- Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related ProblemsSIAM Journal on Computing, 1999
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problemsJournal of the ACM, 1998
- A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fieldsJournal of the ACM, 1995
- Improved routing strategies with succinct tablesJournal of Algorithms, 1990
- A trade-off between space and efficiency for routing tablesJournal of the ACM, 1989