Algorithmic embeddings
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2006.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2007
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/37898 |
| _version_ | 1810983307044716544 |
|---|---|
| author | Bădoiu, Mihai, 1978- |
| author2 | Piotr Indyk. |
| author_facet | Piotr Indyk. Bădoiu, Mihai, 1978- |
| author_sort | Bădoiu, Mihai, 1978- |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2006. |
| first_indexed | 2024-09-23T10:44:27Z |
| format | Thesis |
| id | mit-1721.1/37898 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T10:44:27Z |
| publishDate | 2007 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/378982019-04-12T09:23:09Z Algorithmic embeddings Bădoiu, Mihai, 1978- Piotr Indyk. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2006. Includes bibliographical references (p. 233-242). 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. (cont.) We present results for different types of distortion: multiplicative versus additive, worst-case versus average-case and several types of target metrics, such as the line, the plane, d-dimensional Euclidean space, ultrametrics, and trees. We also present algorithms for ordinal embeddings and embedding with extra information. by Mihai Bădoiu. Ph.D. 2007-07-18T13:06:12Z 2007-07-18T13:06:12Z 2006 2006 Thesis http://hdl.handle.net/1721.1/37898 132692782 eng 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. http://dspace.mit.edu/handle/1721.1/7582 242 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Bădoiu, Mihai, 1978- Algorithmic embeddings |
| title | Algorithmic embeddings |
| title_full | Algorithmic embeddings |
| title_fullStr | Algorithmic embeddings |
| title_full_unstemmed | Algorithmic embeddings |
| title_short | Algorithmic embeddings |
| title_sort | algorithmic embeddings |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/37898 |
| work_keys_str_mv | AT badoiumihai1978 algorithmicembeddings |