Computational metric embeddings
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2008.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2009
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/44712 |
| _version_ | 1811073908111048704 |
|---|---|
| author | Sidiropoulos, Anastasios |
| author2 | Piotr Indyk. |
| author_facet | Piotr Indyk. Sidiropoulos, Anastasios |
| author_sort | Sidiropoulos, Anastasios |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2008. |
| first_indexed | 2024-09-23T09:40:03Z |
| format | Thesis |
| id | mit-1721.1/44712 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T09:40:03Z |
| publishDate | 2009 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/447122019-04-10T13:19:35Z Computational metric embeddings Sidiropoulos, Anastasios 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, 2008. Includes bibliographical references (p. 141-145). We study the problem of computing a low-distortion embedding between two metric spaces. More precisely given an input metric space M we are interested in computing in polynomial time an embedding into a host space M' with minimum multiplicative distortion. This problem arises naturally in many applications, including geometric optimization, visualization, multi-dimensional scaling, network spanners, and the computation of phylogenetic trees. We focus on the case where the host space is either a euclidean space of constant dimension such as the line and the plane, or a graph metric of simple topological structure such as a tree. For Euclidean spaces, we present the following upper bounds. We give an approximation algorithm that, given a metric space that embeds into R1 with distortion c, computes an embedding with distortion c(1) [delta]3/4 (A denotes the ratio of the maximum over the minimum distance). For higher-dimensional spaces, we obtain an algorithm which, for any fixed d > 2, given an ultrametric that embeds into Rd with distortion c, computes an embedding with distortion co(1). We also present an algorithm achieving distortion c logo(1) [delta] for the same problem. We complement the above upper bounds by proving hardness of computing optimal, or near-optimal embeddings. When the input space is an ultrametric, we show that it is NP-hard to compute an optimal embedding into R2 under the ... norm. Moreover, we prove that for any fixed d > 2, it is NP-hard to approximate the minimum distortion embedding of an n-point metric space into Rd within a factor of Q(n1/(17d)). Finally, we consider the problem of embedding into tree metrics. We give a 0(1)approximation algorithm for the case where the input is the shortest-path metric of an unweighted graph. (cont.) For general metric spaces, we present an algorithm which, given an n-point metric that embeds into a tree with distortion c, computes an embedding with distortion (clog n)o ... . By composing this algorithm with an algorithm for embedding trees into R1, we obtain an improved algorithm for embedding general metric spaces into R1. by Anastasios Sidiropoulos. Ph.D. 2009-03-16T19:32:52Z 2009-03-16T19:32:52Z 2008 2008 Thesis http://hdl.handle.net/1721.1/44712 297434536 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 145 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Sidiropoulos, Anastasios Computational metric embeddings |
| title | Computational metric embeddings |
| title_full | Computational metric embeddings |
| title_fullStr | Computational metric embeddings |
| title_full_unstemmed | Computational metric embeddings |
| title_short | Computational metric embeddings |
| title_sort | computational metric embeddings |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/44712 |
| work_keys_str_mv | AT sidiropoulosanastasios computationalmetricembeddings |