Robert Krauthgamer, Nathan Linial and Avner Magen

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-02-1181
May 2002

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2002/CSD-02-1181.pdf

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 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.

BibTeX citation:

@techreport{Krauthgamer:CSD-02-1181,
    Author = {Krauthgamer, Robert and Linial, Nathan and Magen, Avner},
    Title = {Metric Embeddings - Beyond One-dimensional Distortion},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2002},
    Month = {May},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2002/5663.html},
    Number = {UCB/CSD-02-1181},
    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 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.}
}

EndNote citation:

%0 Report
%A Krauthgamer, Robert
%A Linial, Nathan
%A Magen, Avner
%T Metric Embeddings - Beyond One-dimensional Distortion
%I EECS Department, University of California, Berkeley
%D 2002
%@ UCB/CSD-02-1181
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2002/5663.html
%F Krauthgamer:CSD-02-1181