Approximation Algorithms for Low-Distortion Embeddings into Low-Dimensional Spaces
© 2019 Society for Industrial and Applied Mathematics We present several approximation algorithms for the problem of embedding metric spaces into a line, and into the 2-dimensional plane. Among other results, we give an O(n)approximation algorithm for the problem of finding a line embedding of a met...
Main Authors: | Sidiropoulos, Anastasios, Badoiu, Mihai, Dhamdhere, Kedar, Gupta, Anupam, Indyk, Piotr, Rabinovich, Yuri, Racke, Harald, Ravi, R |
---|---|
Other Authors: | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
Format: | Article |
Language: | English |
Published: |
Society for Industrial & Applied Mathematics (SIAM)
2021
|
Online Access: | https://hdl.handle.net/1721.1/135060 |
Similar Items
-
Approximation algorithms for low-distortion embeddings into low-dimensional spaces
by: Sidiropoulos, Anastasios
Published: (2006) -
A Constant-Factor Approximation Algorithm for Embedding Unweighted Graphs into Trees
by: Badoiu, Mihai, et al.
Published: (2004) -
A Constant-Factor Approximation Algorithm for Embedding Unweighted Graphs into Trees
by: Badoiu, Mihai, et al.
Published: (2005) -
Online Embeddings
by: Indyk, Piotr, et al.
Published: (2012) -
Learning-based low-rank approximations
by: Indyk, Piotr
Published: (2021)