Carnegie Mellon University
Browse

Metric Embeddings with Relaxed Guarantees

Download (283.68 kB)
journal contribution
posted on 1973-01-01, 00:00 authored by Ittai Abraham, Yair Bartal, T.H. Hubert Chan, Kedar Dhamdhere, Anupam Gupta, John Kleinberg, Ofer Neiman, Aleksandrs Slivkins
We consider the problem of embedding finite metrics with slack: we seek to produce embeddingswith small dimension and distortion while allowing a (small) constant fraction of all distances to be arbitrarily distorted. This definition is motivated by recent research in the networking community, which achieved striking empirical success at embedding Internet latencies with low distortion into low-dimensional Euclidean space, provided that some small slack is allowed.

History

Publisher Statement

All Rights Reserved

Date

1973-01-01

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC