|
 ABSTRACT
In this paper, we present a polynomial-time approximation algorithm for computing an embedding of an arbitrary metric into a two-dimensional space. The algorithm finds an embedding whose additive distortion is at most cε*, where ε* is the smallest additive distortion possible and c is an absolute constant. To our knowledge, this is the first result of this type, i.e., it gives an algorithm that finds (approximately) optimal embedding of a given distance matrix into a fixed d-dimensional space, where d < 1 is low, under any standard definition of embedding (see Related Work).
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
Richa Agarwala , Vineet Bafna , Martin Farach , Babu Narayanan , Mike Paterson , Mikkel Thorup, On the approximability of numerical taxonomy (fitting distances by tree metrics), Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.365-372, January 28-30, 1996, Atlanta, Georgia, United States
|
| |
2
|
{Bou85} J. Bourgain. On lipschitz embedding of finite metric spaces into hilbert space. Isreal Journal of Mathematics, 52:46--52, 1985.
|
 |
3
|
|
| |
4
|
|
| |
5
|
|
| |
6
|
{Iva00} L. Ivansson. Computational aspects of radiation hybrid. Doctoral Dissertation, Department of Numerical Analysis and Computer Science, Royal Institute of Technology, 2000.
|
| |
7
|
{Kru64a} J.B. Kruskal. Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis. Psychometrika, 29:1--27, 1964.
|
| |
8
|
{Kru64b} J.B. Kruskal. Nonmetric multidimensional scaling: A numerical method. Psychometrika, 29:115--129, 1964.
|
| |
9
|
{Mat90} J. Matoušek. Bi-lipschitz embeddings into low-dimensional euclidean spaces. Comment. Math. Univ. Carolinae, 31:589--600, 1990.
|
| |
10
|
{Mat02} J. Matoušek. Lectures in Discrete Geometry. Springer-Verlag, 2002.
|
| |
11
|
{MDS} Algorithms for multidimensional scaling. http://dimacs.rutgers.edu/Special Years/200l_Data/Algorithms/MDSdescription.html.
|
| |
12
|
{She62a} R. N. Shepard. The analysis of proximities: Multidimensional scaling with an unknown distance function 1. Psychometrika, 27:125--140, 1962.
|
| |
13
|
{She62b} R. N. Shepard. The analysis of proximities: Multidimensional scaling with an unknown distance function 2. Psychometrika, 27:216--246, 1962.
|
CITED BY 9
|
|
Mihai Bǎdoiu , Erik D. Demaine , Mohammad Taghi Hajiaghayi , Piotr Indyk, Low-dimensional embedding with extra information, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA
|
|
|
Thomas Moscibroda , Regina O'Dell , Mirjam Wattenhofer , Roger Wattenhofer, Virtual coordinates for ad hoc and sensor networks, Proceedings of the 2004 joint workshop on Foundations of mobile computing, October 01-01, 2004, Philadelphia, PA, USA
|
|
|
Mihai Bǎdoiu , Kedar Dhamdhere , Anupam Gupta , Yuri Rabinovich , Harald Räcke , R. Ravi , Anastasios Sidiropoulos, Approximation algorithms for low-distortion embeddings into low-dimensional spaces, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
|
|
|
Noga Alon , Mihai Bădoiu , Erik D. Demaine , Martin Farach-Colton , MohammadTaghi Hajiaghayi , Anastasios Sidiropoulos, Ordinal embeddings of minimum relaxation: general properties, trees, and ultrametrics, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
|
|
|
Mihai Bǎdoiu , Julia Chuzhoy , Piotr Indyk , Anastasios Sidiropoulos, Low-distortion embeddings of general metrics into the line, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
|
|
|
|
|
|
MohammadHossein Bateni , MohammadTaghi Hajiaghayi , Erik D. Demaine , Mohammad Moharrami, Plane embeddings of planar graph metrics, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
|
|
|
|
|
|
Noga Alon , Mihai Bădoiu , Erik D. Demaine , Martin Farach-Colton , Mohammadtaghi Hajiaghayi , Anastasios Sidiropoulos, Ordinal embeddings of minimum relaxation: General properties, trees, and ultrametrics, ACM Transactions on Algorithms (TALG), v.4 n.4, p.1-21, August 2008
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
F.2