Local versus global properties of metric spaces

ABSTRACT

Motivated by applications in combinatorial optimization, we initiate a study of the extent to which the global properties of a metric space (especially, embeddability in l1 with low distortion) are determined by the properties of small subspaces. We note connections to similar issues studied already in Ramsey theory, complexity theory (especially PCPs), and property testing. We prove both upper bounds and lower bounds on the distortion of embedding locally constrained metrics into various target spaces.

REFERENCES

• 1: Ingo Althöfer , Gautam Das , David Dobkin , Deborah Joseph , José Soares, On sparse spanners of weighted graphs, Discrete & Computational Geometry, v.9 n.1, p.81-100, 1993 [doi>10.1007/BF02189308]
• 2: Sanjeev Arora , Béla Bollobás , László Lovász, Proving Integrality Gaps without Knowing the Linear Program, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.313-322, November 16-19, 2002
• 3: S. Arora, J. Lee, and A. Naor. Euclidean distortion and sparsest cut. Manuscript, Nov 2004.
• 4: Sanjeev Arora , Satish Rao , Umesh Vazirani, Expander flows, geometric embeddings and graph partitioning, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, p.222-231, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007355]
• 5: Yonatan Aumann , Yuval Rabani, An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm, SIAM Journal on Computing, v.27 n.1, p.291-301, Feb. 1998 [doi>10.1137/S0097539794285983]
• 6: Yair Bartal , Nathan Linial , Manor Mendel , Assaf Naor, On metric ramsey-type phenomena, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780610]
• 7: S. Chawla, A. Gupta, and H. Räcke. An improved approximation to sparsest cut. In Proc. of the 16th Ann. ACM-SIAM Symp. on Discrete Algorithms, January 2005.
• 8: Shuchi Chawla , Robert Krauthgamer , Ravi Kumar , Yuval Rabani , D. Sivakumar, On the Hardness of Approximating Multicut and Sparsest-Cut, Proceedings of the 20th Annual IEEE Conference on Computational Complexity, p.144-153, June 11-15, 2005 [doi>10.1109/CCC.2005.20]
• 9: Chandra Chekuri , Anupam Gupta , Ilan Newman , Yuri Rabinovich , Alistair Sinclair, Embedding k-outerplanar graphs into ℓ1, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 10: M. M. Deza and M. Laurent. Geometry of Cuts and Metrics. Springer Verlag, 1997.
• 11: M. M. Deza and H. Maehara. Metric transform and Euclidean embeddings. Transactions of the American Mathematical Society, 317:661--671, 1990.
• 12: 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]
• 13: M. Farach-Colton. (Nearly) optimal embeddings into additive and ultrametric trees. DIMACS Workshop on Discrete Metric Embeddings, Princeton, August 2003.
• 14: Anupam Gupta , Alistair Sinclair, Embeddings of finite metrics, 2000
• 15: Anupam Gupta , Alistair Sinclair , Ilan Newman , Yuri Rabinovich, Cuts, Trees and -Embeddings of Graphs, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.399, October 17-18, 1999
• 16: R. C. James. Uniformly non-square Banach spaces. Annals of Mathematics, 80:542--550, 1964.
• 17: W. B. Johnson and G. Schechtman. Private communication, 2003.
• 18: N. Linial, E. London, and Yu. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215--245, 1995.
• 19: Subhash Khot, On the power of unique 2-prover 1-round games, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510017]
• 20: J. Matousek. Ramsey-like properties for bi-Lipschitz mappings of finite metric spaces. Comment. Math. Univ. Carolinae, 33:451--463, 1992.
• 21: Vitali D Milman , Gideon Schechtman, Asymptotic theory of finite dimensional normed spaces, Springer-Verlag New York, Inc., New York, NY, 1986
• 22: Y. Rabinovich and R. Raz. Lower bounds on distortion of embedding finite metric spaces in graphs. Discrete and Computational Geometry, 19:79--94, 1998.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Theory