Bypassing the embedding: algorithms for low dimensional metrics

ABSTRACT

The doubling dimension of a metric is the smallest k such that any ball of radius 2r can be covered using 2^k 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.

REFERENCES

• 1: Noga Alon , Richard M. Karp , David Peleg , Douglas West, A Graph-Theoretic Game and its Application to the $k$-Server Problem, SIAM Journal on Computing, v.24 n.1, p.78-100, Feb. 1995 [doi>10.1137/S0097539792224474]
• 2: S. Arora, Polynomial time approximation schemes for Euclidean TSP and other geometric problems, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.2, October 14-16, 1996
• 3: Sanjeev Arora, Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems, Journal of the ACM (JACM), v.45 n.5, p.753-782, Sept. 1998 [doi>10.1145/290179.290180]
• 4: S. Arora. Approximation schemes for NP-hard geometric optimization problems: a survey. Mathematical Programming, 97(1--2):43--69, 2003.
• 5: Sanjeev Arora , Prabhakar Raghavan , Satish Rao, Approximation schemes for Euclidean k-medians and related problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.106-113, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276718]
• 6: P. Assouad. Plongements lipschitziens dans Rn. Bull. Soc. Math. France, 111(4):429--448, 1983.
• 7: Baruch Awerbuch , Amotz Bar Noy , Nathan Linial , David Peleg, Improved routing strategies with succinct tables, Journal of Algorithms, v.11 n.3, p.307-341, Sep. 1990 [doi>10.1016/0196-6774(90)90017-9]
• 8: Baruch Awerbuch , David Peleg, Routing with polynomial communication-space trade-off, SIAM Journal on Discrete Mathematics, v.5 n.2, p.151-162, May 1992 [doi>10.1137/0405013]
• 9: Y. Bartal, Probabilistic approximation of metric spaces and its algorithmic applications, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.184, October 14-16, 1996
• 10: Yair Bartal, On approximating arbitrary metrices by tree metrics, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.161-168, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276725]
• 11: Andrei Z. Broder , Moses Charikar , Alan M. Frieze , Michael Mitzenmacher, Min-wise independent permutations, Journal of Computer and System Sciences, v.60 n.3, p.630-659, June 2000 [doi>10.1006/jcss.1999.1690]
• 12: Gruia Calinescu , Howard Karloff , Yuval Rabani, Approximation algorithms for the 0-extension problem, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.8-16, January 07-09, 2001, Washington, D.C., United States
• 13: Paul B. Callahan , S. Rao Kosaraju, A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields, Journal of the ACM (JACM), v.42 n.1, p.67-90, Jan. 1995 [doi>10.1145/200836.200853]
• 14: Moses Charikar , Chandra Chekuri , Ashish Goel , Sudipto Guha , Serge Plotkin, Approximating a Finite Metric by a Small Number of Tree Metrics, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.379, November 08-11, 1998
• 15: K. L. Clarkson. Nearest neighbor queries in metric spaces. Discrete Comput. Geom., 22(1):63--93, 1999.
• 16: Lenore J. Cowen, Compact routing with minimum stretch, Journal of Algorithms, v.38 n.1, p.170-183, Jan. 2001 [doi>10.1006/jagm.2000.1134]
• 17: Tamar Eilam , Cyril Gavoille , David Peleg, Compact routing schemes with low stretch factor (extended abstract), Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.11-20, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277697.277702]
• 18: Jittat Fakcharoenphol , Chris Harrelson , Satish Rao , Kunal Talwar, An improved approximation algorithm for the 0-extension problem, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 19: Jittat Fakcharoenphol , Satish Rao , Kunal Talwar, A tight bound on approximating arbitrary metrics by tree metrics, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780608]
• 20: Cyril Gavoille , Michal Katz , Nir A. Katz , Christophe Paul , David Peleg, Approximate Distance Labeling Schemes, Proceedings of the 9th Annual European Symposium on Algorithms, p.476-487, August 28-31, 2001
• 21: Cyril Gavoille , David Peleg, Compact and localized distributed data structures, Distributed Computing, v.16 n.2-3, p.111-120, September 2003 [doi>10.1007/s00446-002-0073-5]
• 22: Cyril Gavoille , David Peleg , Stéphane Pérennes , Ran Raz, Distance labeling in graphs, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.210-219, January 07-09, 2001, Washington, D.C., United States
• 23: Joachim Gudmundsson , Christos Levcopoulos , Giri Narasimhan , Michiel Smid, Approximate distance oracles for geometric graphs, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.828-837, January 06-08, 2002, San Francisco, California
• 24: Anupam Gupta , Robert Krauthgamer , James R. Lee, Bounded Geometries, Fractals, and Low-Distortion Embeddings, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.534, October 11-14, 2003
• 25: Sariel Har-Peled , Soham Mazumdar, On coresets for k-means and k-median clustering, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007400]
• 26: Kirsten Hildrum , John Kubiatowicz , Sean Ma , Satish Rao, A note on the nearest neighbor in growth-restricted metrics, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 27: Piotr Indyk, Algorithms for dynamic geometric problems over data streams, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007413]
• 28: David R. Karger , Matthias Ruhl, Finding nearest neighbors in growth-restricted metrics, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510013]
• 29: Stavros G. Kolliopoulos , Satish Rao, A Nearly Linear-Time Approximation Scheme for the Euclidean kappa-median Problem, Proceedings of the 7th Annual European Symposium on Algorithms, p.378-389, July 16-18, 1999
• 30: Robert Krauthgamer , James R. Lee, Navigating nets: simple algorithms for proximity search, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 31: R. Krauthgamer and J. Lee. Nearest neighbour search in the blackbox model. Manuscript, 2004.
• 32: T. J. Laakso. Plane with A∞-weighted metric not bi-Lipschitz embeddable to RN. Bull. London Math. Soc., 34(6):667--676, 2002.
• 33: U. Lang and C. Plaut. Bilipschitz embeddings of metric spaces into space forms. Geom. Dedicata, 87(1-3):285--307, 2001.
• 34: N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215--245, 1995.
• 35: Joseph S. B. Mitchell, Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems, SIAM Journal on Computing, v.28 n.4, p.1298-1309, Aug. 1999 [doi>10.1137/S0097539796309764]
• 36: T. S. E. Ng and H. Zhang. Predicting internet network distance with coordinates-based approaches. In 21st Annual Joint Conference of the IEEE Computer and Communications Society (INFOCOM-02), pages 170--179, 2002.
• 37: David Peleg, Distributed computing: a locality-sensitive approach, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 38: D. Peleg. Proximity preserving labeling schemes. Journal of Graph Theory, 33:167--176, 2000.
• 39: David Peleg , Eli Upfal, A trade-off between space and efficiency for routing tables, Journal of the ACM (JACM), v.36 n.3, p.510-530, July 1989 [doi>10.1145/65950.65953]
• 40: Serge A. Plotkin , David B. Shmoys , Éva Tardos, Fast approximation algorithms for fractional packing and covering problems, Mathematics of Operations Research, v.20 n.2, p.257-301, May 1995 [doi>10.1287/moor.20.2.257]
• 41: Satish B. Rao , Warren D. Smith, Approximating geometrical graphs via “spanners” and “banyans”, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.540-550, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276868]
• 42: J. B. Tenenbaum, V. de Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500):2319--2323, 2000.
• 43: Mikkel Thorup , Uri Zwick, Approximate distance oracles, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.183-192, July 2001, Hersonissos, Greece [doi>10.1145/380752.380798]
• 44: Mikkel Thorup , Uri Zwick, Compact routing schemes, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.1-10, July 2001, Crete Island, Greece [doi>10.1145/378580.378581]
• 45: Luca Trevisan, When Hamming Meets Euclid: The Approximability of Geometric TSP and Steiner Tree, SIAM Journal on Computing, v.30 n.2, p.475-485, 2000 [doi>10.1137/S0097539799352735]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

General Terms:
Algorithms, Theory

Keywords:
PTAS, TSP, distance labels, doubling metrics, routing schemes