{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:40:51Z","timestamp":1787323251726,"version":"build-2736575974"},"reference-count":40,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"name":"Paris Kanellakis Fellowship Fund"},{"DOI":"10.13039\/501100005302","name":"Alexander S. Onassis Public Benefit Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100005302","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCR-0085982"],"award-info":[{"award-number":["CCR-0085982"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCR-0122581"],"award-info":[{"award-number":["CCR-0122581"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCR-0085982"],"award-info":[{"award-number":["CCR-0085982"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCR-0122581"],"award-info":[{"award-number":["CCR-0122581"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCR-0085982"],"award-info":[{"award-number":["CCR-0085982"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCR-0122581"],"award-info":[{"award-number":["CCR-0122581"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF 04-30751"],"award-info":[{"award-number":["CCF 04-30751"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1423230"],"award-info":[{"award-number":["CCF-1423230"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CAREER-1453472"],"award-info":[{"award-number":["CAREER-1453472"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2019,1]]},"abstract":"<jats:p>We present several approximation algorithms for the problem of embedding metric spaces into a line, and into the 2-dimensional plane. Among other results, we give an $O(\\sqrt{n})$-approximation algorithm for the problem of finding a line embedding of a metric induced by a given unweighted graph, that minimizes the (standard) multiplicative distortion. We give an improved $\\tilde{O}(n^{1\/3})$ approximation for the case of metrics induced by unweighted trees.<\/jats:p>","DOI":"10.1137\/17m1113527","type":"journal-article","created":{"date-parts":[[2019,3,7]],"date-time":"2019-03-07T14:10:03Z","timestamp":1551967803000},"page":"454-473","source":"Crossref","is-referenced-by-count":1,"title":["Approximation Algorithms for Low-Distortion Embeddings into Low-Dimensional Spaces"],"prefix":"10.1137","volume":"33","author":[{"given":"Anastasios","family":"Sidiropoulos","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mihai","family":"Badoiu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kedar","family":"Dhamdhere","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anupam","family":"Gupta","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Piotr","family":"Indyk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuri","family":"Rabinovich","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Harald","family":"Racke","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"R.","family":"Ravi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2019,3,7]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795296334"},{"key":"atypb2","first-page":"225","author":"Badoiu M.","year":"2005","journal-title":"New York"},{"key":"atypb3","first-page":"187","author":"Badoiu M.","year":"2006","journal-title":"New York"},{"key":"atypb5","first-page":"512","author":"Badoiu M.","year":"2007","journal-title":"Philadelphia"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.4064\/fm-20-1-177-190"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1007\/BF02776078"},{"key":"atypb8","first-page":"434","author":"B\u0103doiu M.","year":"2003","journal-title":"Philadelphia"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20608"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"K. Dhamdhere,\n                      Approximating additive distortion of embeddings into line metrics\n                      , in 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), Springer, Berlin, 2004.","DOI":"10.1007\/978-3-540-27821-4_9"},{"key":"atypb11","first-page":"222","author":"Edmonds J.","year":"2010","journal-title":"Philadelphia"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"M. Farach-Colton, S. Kannan, and T. Warnow,\n                      A robust model for finding optimal evolutionary tree\n                      , Proceedings of the Symposium on Theory of Computing, ACM, New York, 1993.","DOI":"10.1145\/167088.167132"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1682"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1145\/2489789"},{"key":"atypb15","first-page":"112","author":"Fomin F. V.","year":"2009","journal-title":"Springer"},{"key":"atypb16","first-page":"788","author":"Gupta A.","year":"2000","journal-title":"Philadelphia"},{"key":"atypb17","first-page":"465","author":"Hastad J.","year":"1998","journal-title":"Berlin"},{"key":"atypb18","unstructured":"A. Hall and C. H. Papadimitriou,\n                      Approximating the distortion\n                      , in Approximation, Randomization and Combinatorial Optimization, Algorithms and Techniques, Proceedings of the 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2005 and 9th InternationalWorkshop on Randomization and Computation, RANDOM 2005, Berkeley, CA, Springer, Berlin, 2005, pp. 111-122."},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"S. Har-Peled,\n                      Geometric Approximation Algorithms\n                      , Math. Surveys Monogr. 173, American Mathematical Society, Providence, RI, 2011.","DOI":"10.1090\/surv\/173"},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"P. Indyk,\n                      Tutorial: Algorithmic applications of low-distortion geometric embeddings\n                      , in Proceedings of the Symposium on Foundations of Computer Science, IEEE Computing Society, Los Alamitos, CA, 2001, pp. 10-33.","DOI":"10.1109\/SFCS.2001.959878"},{"key":"atypb21","unstructured":"L. Ivansson,\n                      Computational Aspects of Radiation Hybrid\n                      , Doctoral Dissertation, Department of Numerical Analysis and Computer Science, KTH Royal Institute of Technology, Stockholm, Sweden, 2000."},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.4064\/fm-22-1-77-108"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1137\/080712921"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289565"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289694"},{"key":"atypb26","doi-asserted-by":"crossref","unstructured":"S. Khot and R. Saket,\n                      Hardness of embedding metric spaces of equal size\n                      , in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Proceedings of the 10th International Workshop, APPROX 2007, and 11th International Workshop, RANDOM 2007, Princeton, NJ, Springer, Berlin, 2007, pp. 218-227.","DOI":"10.1007\/978-3-540-74208-1_16"},{"key":"atypb27","doi-asserted-by":"crossref","unstructured":"N. Linial, E. London, and Y. Rabinovich,\n                      The geometry of graphs and some of its algorithmic applications\n                      , in Proceedings of 35th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 1994, pp. 577-591.","DOI":"10.1109\/SFCS.1994.365733"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1137\/16M1104834"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1016\/j.crma.2004.03.005"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1007\/s000390050018"},{"key":"atypb31","first-page":"589","volume":"31","author":"Matou\u0161ek J.","year":"1990","journal-title":"Comment. Math. Univ. Carolin."},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1007\/BF02761110"},{"key":"atypb33","unstructured":"J. Matou\u0161ek,\n                      Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry\n                      , Springer, New York, 2003."},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(99)00002-4"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-2010-05186-4"},{"key":"atypb36","first-page":"729","author":"Nayyeri A.","year":"2015","journal-title":"NJ"},{"key":"atypb37","first-page":"28","author":"Onak K.","year":"2008","journal-title":"New York"},{"key":"atypb38","first-page":"112","author":"Papadimitriou C. H.","year":"2005","journal-title":"Philadelphia"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1137\/0601042"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289630"},{"key":"atypb41","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1017\/S0033312300004208","volume":"27","author":"Shepard R. N.","year":"1962","journal-title":"Psychometrika"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1113527","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:50:54Z","timestamp":1787320254000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1113527"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["10.1137\/17M1113527"],"URL":"https:\/\/doi.org\/10.1137\/17m1113527","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1]]}}}