Algorithmic embeddings

We present several computationally efficient algorithms, and complexity results on low distortion mappings between metric spaces. An embedding between two metric spaces is a mapping between the two metric spaces and the distortion of the embedding is the factor by which the distances change. We have pioneered theoretical work on relative (or approximation) version of this problem. In this setting, the question is the following: for the class of metrics C, and a host metric M', what is the smallest approximation factor a > 1 of an efficient algorithm minimizing the distortion of an embedding of a given input metric M E C into M'? This formulation enables the algorithm to adapt to a given input metric. In particular, if the host metric is "expressive enough" to accurately model the input distances, the minimum achievable distortion is low, and the algorithm will produce an embedding with low distortion as well. This problem has been a subject of extensive applied research during the last few decades. However, almost all known algorithms for this problem are heuristic. As such, they can get stuck in local minima, and do not provide any global guarantees on solution quality. We investigate several variants of the above problem, varying different host and target metrics, and definitions of distortion.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2006

Author dc:creator

• Bădoiu, Mihai, 1978-

Advisor dc:contributor.advisor

• Piotr Indyk.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/37898

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/37898