On average distortion of embedding metrics into the line and into L₁

ABSTRACT

We introduce and study the notion of the average distortion of a nonexpanding embedding of one metric space into another. Less sensitive than the multiplicative metric distortion, the average distortion captures well the global picture, and, overall, is a quite interesting new measure of metric proximity, related to the concentration of measure phenomenon. We establish close mutual relations between the MinCut- MaxFlow gap in a uniform-demand multicommodity flow, and the average distortion of embedding the suitable (dual) metric into l₁. These relations are exploited to show that the shortest-path metrics of special (e.g., planar, bounded treewidth, etc.) graphs embed into l₁ with constant average distortion. The main result of the paper claims that this remains true even if l₁ is replaced with the line. This result is further sharpened for graphs of a bounded treewidth.

References

1. J. Bourgain. On Lipschitz embeddings of finite metric spaces in Hilbert space. Israel Journal of Mathematics, 52(1-2):46--52, 1985.
2. C. Chekuri, A. Gupta, I. Newman, Y. Rabinovich, and A. Sinclair. Embedding k-outerplanar graphs into l_1, 2003. In Proceedings of the 14th Annual Symposium on Discrete Algorithms, pages 527-536. ACM, 2003.
3. M. Gromov. Metric structures for Riemannian and non-Riemannian spaces. Birkhäuser, Boston, Massachusetts, 1999.
4. A. Gupta, I. Newman, Y. Rabinovich, and A. Sinclair. Cuts, trees and l_1-embeddings of graphs. In Proceedings of the 40th Annual Symposium on Foundations of CS, pages 399--408. IEEE, 1999.
5. P. Indyk. Algorithmic aspects of geometric embeddings. In Proceedings of the~42th~Annual Symposium on Foundations of Computer Science. IEEE, 2001.
6. P. Klein, S. A. Plotkin, and S. B. Rao. Excluded minors, network decomposition, and multicommodity flow. In Proceedings of the~25th~Annual Symposium on Theory of Computing, pages 682--690. ACM, 1993.
7. F. T. Leighton and S. B. Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Journal of the ACM, 46(6):787--832, 1999.
8. N. Linial, E. London, , and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215--245, 1995.
9. J. Matoušek. Lectures on Discrete Geometry. Springer-Verlag, 2002.
10. J. Matoušek and Y. Rabinovich. On dominated l_1 metrics. Israel Journal of Mathematics, 123:285--301, 2001.
11. V. Milman and G. Schechtman. Asymptotic Theory of Finite Dimensional Spaces. Springer-Verlag, 1986.
12. I. Newman and Y. Rabinovich. A lower bound on the distortion of embedding planar metrics into euclidean space. Discrete and Computational Geometry, 29:77--81, 2003.
13. S. B. Rao. Small distortion and volume preserving embeddings for planar and euclidean metrics. In Proceedings of the 15th Annual Symposium on Computational Geometry, pages 300--302. ACM, 1999.

Index Terms

• Information systems

  • Data management systems

    • Database design and models

      • Physical data models

• Theory of computation

  • Randomness, geometry and discrete structures

    • Computational geometry