{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:37:00Z","timestamp":1750307820293,"version":"3.41.0"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2008,8,1]],"date-time":"2008-08-01T00:00:00Z","timestamp":1217548800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Cybertrust","award":["6.28E+26"],"award-info":[{"award-number":["6.28E+26"]}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["4.30E+19"],"award-info":[{"award-number":["4.30E+19"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2008,8]]},"abstract":"<jats:p>In the last decade, the notion of metric embeddings with small distortion has received wide attention in the literature, with applications in combinatorial optimization, discrete mathematics, and bio-informatics. The notion of embedding is, given two metric spaces on the same number of points, to find a bijection that minimizes maximum Lipschitz and bi-Lipschitz constants. One reason for the popularity of the notion is that algorithms designed for one metric space can be applied to a different one, given an embedding with small distortion. The better distortion, the better the effectiveness of the original algorithm applied to a new metric space.<\/jats:p>\n          <jats:p>\n            The goal recently studied by Kenyon et al. [2004] is to consider all possible embeddings between two\n            <jats:italic>finite<\/jats:italic>\n            metric spaces and to find the best possible one; that is, consider a single objective function over the space of all possible embeddings that minimizes the distortion. In this article we continue this important direction. In particular, using a theorem of Albert and Atkinson [2005], we are able to provide an algorithm to find the optimal bijection between two line metrics, provided that the optimal distortion is smaller than 13.602. This improves the previous bound of 3 + 2\u221a2, solving an open question posed by Kenyon et al. [2004]. Further, we show an inherent limitation of algorithms using the \u201cforbidden pattern\u201d based dynamic programming approach, in that they cannot find optimal mapping if the optimal distortion is more than 7 + 4\u221a3 (\u2243 13.928). Thus, our results are almost optimal for this method. We also show that previous techniques for general embeddings apply to a (slightly) more general class of metrics.\n          <\/jats:p>","DOI":"10.1145\/1383369.1383376","type":"journal-article","created":{"date-parts":[[2008,8,27]],"date-time":"2008-08-27T11:56:36Z","timestamp":1219838196000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Improved algorithms for optimal embeddings"],"prefix":"10.1145","volume":"4","author":[{"given":"Nishanth","family":"Chandran","sequence":"first","affiliation":[{"name":"University of California, Los Angeles, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ryan","family":"Moriarty","sequence":"additional","affiliation":[{"name":"University of California, Los Angeles, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rafail","family":"Ostrovsky","sequence":"additional","affiliation":[{"name":"University of California, Los Angeles, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Omkant","family":"Pandey","sequence":"additional","affiliation":[{"name":"University of California, Los Angeles, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohammad Ali","family":"Safari","sequence":"additional","affiliation":[{"name":"University of Alberta, Alberta, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amit","family":"Sahai","sequence":"additional","affiliation":[{"name":"University of California, Los Angeles, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,8,22]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(02)00282-2"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2005.06.016"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060624"},{"volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM.","author":"Badoiu M.","key":"e_1_2_1_4_1","unstructured":"Badoiu , M. , Dhamdhere , K. , Gupta , A. , Rabinovich , Y. , Racke , H. , Ravi , R. , and Sidiropoulos , A . 2005. Approximation algorithms for low-distortion embeddings into low-dimensional spaces . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM. Badoiu, M., Dhamdhere, K., Gupta, A., Rabinovich, Y., Racke, H., Ravi, R., and Sidiropoulos, A. 2005. Approximation algorithms for low-distortion embeddings into low-dimensional spaces. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.993558"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00209-3"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780620"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190060302"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/568522.568523"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/11538462_10"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/276884.276911"},{"key":"e_1_2_1_13_1","unstructured":"Horn R. A. and Johnson C. R. 1986. Matrix Analysis. Cambridge University Press New York.   Horn R. A. and Johnson C. R. 1986. Matrix Analysis. Cambridge University Press New York."},{"key":"e_1_2_1_14_1","unstructured":"Johnson W. and Lindenstrauss J. 2003. Handbook of Geometry of Banach Spaces. North-Holland.  Johnson W. and Lindenstrauss J. 2003. Handbook of Geometry of Banach Spaces. North-Holland."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007398"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289565"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289694"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the International Congress of Mathematicians III, 573--586","author":"Linial N.","year":"2002","unstructured":"Linial , N. 2002 . Finite metric spaces\u2014Combinatorics, geometry and algorithms . In Proceedings of the International Congress of Mathematicians III, 573--586 . Linial, N. 2002. Finite metric spaces\u2014Combinatorics, geometry and algorithms. In Proceedings of the International Congress of Mathematicians III, 573--586."},{"volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM.","author":"Papadimitriou C.","key":"e_1_2_1_19_1","unstructured":"Papadimitriou , C. , and Safra , S . 2005. The complexity of low-distortion embeddings between point sets . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM. Papadimitriou, C., and Safra, S. 2005. The complexity of low-distortion embeddings between point sets. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(93)90516-V"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289630"},{"key":"e_1_2_1_22_1","first-page":"216","article-title":"The analysis of proximities: Multidimensional scaling with an unknown distance function 2","volume":"27","author":"Shepard R.","year":"1962","unstructured":"Shepard , R. 1962 b. The analysis of proximities: Multidimensional scaling with an unknown distance function 2 . Pyschometrika 27 , 216 -- 246 . Shepard, R. 1962b. The analysis of proximities: Multidimensional scaling with an unknown distance function 2. Pyschometrika 27, 216--246.","journal-title":"Pyschometrika"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1383369.1383376","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1383369.1383376","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:57:46Z","timestamp":1750255066000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1383369.1383376"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,8]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,8]]}},"alternative-id":["10.1145\/1383369.1383376"],"URL":"https:\/\/doi.org\/10.1145\/1383369.1383376","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2008,8]]},"assertion":[{"value":"2006-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-08-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}