Multi-embedding and path approximation of metric spaces

ABSTRACT

Metric embeddings have become a frequent tool in the design of algorithms. The applicability is often dependent on how high the embedding's distortion is. For example embedding into ultrametrics (or arbitrary trees) requires linear distortion. Using probabilistic metric embeddings, the bound reduces to O(log nlog logn). Yet, the lower bound is still logarithmic.We make a step further in the direction of bypassing this difficulty. We define "multi-embeddings" of metric spaces where a point is mapped onto a set of points, while keeping the target metric being of polynomial size and preserving the distortion of paths. The distortion obtained with such multi-embeddings into ultrametrics is at most O(log Δ log log Δ) where δ is the (normalized) diameter, and probabilistically O(log n log log log n). In particular, for expander graphs, we are able to obtain constant distortions embeddings into trees vs. the Ω(logn) lower bound for all previous notions of embeddings.We demonstrate the algorithmic application of the new embeddings by obtaining improvements for two well-known problems: group Steiner tree and metrical task systems.

REFERENCES

• 1: 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
• 2: 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]
• 3: Yair Bartal , Avrim Blum , Carl Burch , Andrew Tomkins, A polylog(n)-competitive algorithm for metrical task systems, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.711-719, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258667]
• 4: Y. Barta , B. Bollobás, A Ramsey-Type Theorem for Metric Spaces and its Applications for Metrical Task Systems and Related Problems, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.396, October 14-17, 2001
• 5: Y. Bartal, N. Linial, M. Mendel, and A. Naor. On metric Ramsey-type phenomena. Manuscript, 2002.
• 6: Allan Borodin , Nathan Linial , Michael E. Saks, An optimal on-line algorithm for metrical task system, Journal of the ACM (JACM), v.39 n.4, p.745-763, Oct. 1992 [doi>10.1145/146585.146588]
• 7: J. Bourgain. On lipschitz embedding of finite metric spaces in hilbert space. Israel J. Math., 52:46--52, 1985.
• 8: 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
• 9: F. R. K. Chung. Diameters and eigenvalues. J. Amer. Math. Soc., 2(2):187--196, 1989.
• 10: Uriel Feige, A threshold of ln n for approximating set cover, Journal of the ACM (JACM), v.45 n.4, p.634-652, July 1998 [doi>10.1145/285055.285059]
• 11: Amos Fiat , Manor Mendel, Better algorithms for unfair metrical task systems and applications, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.725-734, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335408]
• 12: Naveen Garg , Goran Konjevod , R. Ravi, A polylogarithmic approximation algorithm for the group Steiner tree problem, Journal of Algorithms, v.37 n.1, p.66-84, Oct. 2000 [doi>10.1006/jagm.2000.1096]
• 13: Eran Halperin , Guy Kortsarz , Robert Krauthgamer , Aravind Srinivasan , Nan Wang, Integrality ratio for group Steiner trees and directed steiner trees, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 14: P. Indyk, Algorithmic Applications of Low-Distortion Geometric Embeddings, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.10, October 14-17, 2001
• 15: D.S. Johnson. Approximation algorithms for combinatorial problems. Journal of Computer ans System Science, 9:256--278, 1974.
• 16: N. Linial. Finite metric spaces - combinatorics, geometry and algorithms. In ICM, 2002.
• 17: N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215--245, 1995.
• 18: Y. Rabinovich and R. Raz. Lower bounds on the distortion of embedding finite metric spaces in graphs. Discrete Comput. Geom., 19(1):79--94, 1998.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.3 Applications

Additional Classification:
  G. Mathematics of Computing
  G.m MISCELLANEOUS

General Terms:
Algorithms, Theory