Now showing items 1-1 of 1

    • Metric Embeddings with Relaxed Guarantees 

      Chan, T-H. Hubert; Dhamdhere, Kedar; Gupta, Anupam; Kleinberg, Jon; Slivkins, Aleksandrs Aleksandrs Slivkins (Cornell University, 2006-09-22)
      We consider the problem of embedding finite metrics with "slack": we seek to produce embeddings with small dimension and distortion while allowing a (small) constant fraction of all distances to be arbitrarily distorted. ...