Metric Embeddings - Beyond One-Dimensional Distortion
Abstract
Metric spaces and their embeddings have recently played a prominent role in the development of new algorithms. So far, most of the emphasis was on embeddings that preserve pairwise distances. A very intriguing concept introduced by Feige [Fei00], allows us to quantify the extent to which higher-dimensional structures are preserved by a given embedding. We investigate this concept for several basic graph families such as paths, trees, cubes and expanders.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 15, 2002
- Accession Number
- ADA619309
Entities
People
- Avner Magen
- Nathan Linial
- Robert Krauthgamer
Organizations
- University of California, Berkeley