{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/44712"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/44712","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Computational metric embeddings","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Sidiropoulos, Anastasios"],"institution":"Massachusetts Institute of Technology","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.","school":null,"contributors":[],"advisors":["Piotr Indyk."],"committee_chairs":[],"committee_members":[],"year":2008,"date_issued":"2008","date_published":"2008","updated_at":"2026-07-22T22:21:05Z","subjects":["Electrical Engineering and Computer Science."],"languages":["eng"],"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."],"rights_urls":["http://dspace.mit.edu/handle/1721.1/7582"],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/1721.1/44712","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Piotr Indyk."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."]},{"key":"dc:creator","label":"Author","values":["Sidiropoulos, Anastasios"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2009-03-16T19:32:52Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2009-03-16T19:32:52Z"]},{"key":"dc:date.issued","label":"Date","values":["2008"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Electrical Engineering and Computer Science."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["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."]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://dspace.mit.edu/handle/1721.1/7582"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/1721.1/44712"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2008.","Includes bibliographical references (p. 141-145)."]},{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Ph.D."]},{"key":"dc:title","label":"Title","values":["Computational metric embeddings"]}]}],"canonical_facts":{"dc:contributor.advisor":["Piotr Indyk."],"dc:contributor.department":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."],"dc:contributor.other":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."],"dc:creator":["Sidiropoulos, Anastasios"],"dc:date.accessioned":["2009-03-16T19:32:52Z"],"dc:date.available":["2009-03-16T19:32:52Z"],"dc:date.issued":["2008"],"dc:description":["Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2008.","Includes bibliographical references (p. 141-145)."],"dc:description.abstract":["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."],"dc:description.degree":["Ph.D."],"dc:identifier.uri":["http://hdl.handle.net/1721.1/44712"],"dc:language.iso":["eng"],"dc:publisher":["Massachusetts Institute of Technology"],"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."],"dc:rights.uri":["http://dspace.mit.edu/handle/1721.1/7582"],"dc:subject":["Electrical Engineering and Computer Science."],"dc:title":["Computational metric embeddings"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:21:05Z"}