{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:43Z","timestamp":1740109303868,"version":"3.37.3"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"11","license":[{"start":{"date-parts":[[2021,7,26]],"date-time":"2021-07-26T00:00:00Z","timestamp":1627257600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,7,26]],"date-time":"2021-07-26T00:00:00Z","timestamp":1627257600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["524\/15","1817\/17"],"award-info":[{"award-number":["524\/15","1817\/17"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2015813"],"award-info":[{"award-number":["2015813"]}],"id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,11]]},"DOI":"10.1007\/s00453-021-00843-6","type":"journal-article","created":{"date-parts":[[2021,7,26]],"date-time":"2021-07-26T20:03:28Z","timestamp":1627329808000},"page":"3319-3337","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Near Isometric Terminal Embeddings for Doubling Metrics"],"prefix":"10.1007","volume":"83","author":[{"given":"Michael","family":"Elkin","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4179-4364","authenticated-orcid":false,"given":"Ofer","family":"Neiman","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,7,26]]},"reference":[{"key":"843_CR1","doi-asserted-by":"crossref","unstructured":"Abboud, Amir., Bodwin, Greg.: Reachability preservers: New extremal bounds and approximation algorithms. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1865\u20131883, 2018","DOI":"10.1137\/1.9781611975031.122"},{"key":"843_CR2","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/BF02189308","volume":"9","author":"I Alth\u00f6fer","year":"1993","unstructured":"Alth\u00f6fer, I., Das, G., Dobkin, D., Joseph, D., Soares, J.: On sparse spanners of weighted graphs. Dis. Comput. Geom. 9, 81\u2013100 (1993)","journal-title":"Dis. Comput. Geom."},{"issue":"4","key":"843_CR3","doi-asserted-by":"publisher","first-page":"429","DOI":"10.24033\/bsmf.1997","volume":"111","author":"P Assouad","year":"1983","unstructured":"Assouad, P.: Plongements lipschitziens dans $$\\mathbb{R}^n$$. Bull. Soc. Math. France 111(4), 429\u2013448 (1983)","journal-title":"Bull. Soc. Math. France"},{"key":"843_CR4","unstructured":"Bartal, Y.: Probabilistic approximation of metric spaces and its algorithmic applications. In: Proceedings of the 37th IEEE Symp. on Foundations of Computer Science, pp. 184\u2013193, 1996"},{"issue":"1\u20132","key":"843_CR5","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1007\/BF02776078","volume":"52","author":"J Bourgain","year":"1985","unstructured":"Bourgain, J.: On lipschitz embedding of finite metric spaces in hilbert space. Israel J. Math. 52(1\u20132), 46\u201352 (1985)","journal-title":"Israel J. Math."},{"key":"843_CR6","doi-asserted-by":"crossref","unstructured":"Chandra, Barun., Das, Gautam., Narasimhan, Giri., Soares, Jos\u00e9.: New sparseness results on graph spanners. In: Proc. of 8th SOCG, pp. 192\u2013201, 1992","DOI":"10.1145\/142675.142717"},{"key":"843_CR7","unstructured":"Coppersmith, D., Elkin, M.: Sparse source-wise and pair-wise distance preservers. In: SODA: ACM-SIAM Symposium on Discrete Algorithms, pp. 660\u2013669, 2005"},{"key":"843_CR8","doi-asserted-by":"crossref","unstructured":"Chan, T-H. Hubert., Gupta, Anupam.: Small hop-diameter sparse spanners for doubling metrics. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, SODA \u201906, pp. 70\u201378, Philadelphia, PA, USA, 2006. Society for Industrial and Applied Mathematics","DOI":"10.1145\/1109557.1109566"},{"key":"843_CR9","unstructured":"Cygan, Marek., Grandoni, Fabrizio., Kavitha, Telikepalli.: On pairwise spanners. In: 30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013, February 27\u2013March 2, 2013, Kiel, Germany, pp. 209\u2013220, 2013"},{"issue":"4","key":"843_CR10","first-page":"55:1","volume":"12","author":"T-H Chan","year":"2016","unstructured":"Chan, T.-H., Gupta, A., Maggs, B.M., Zhou, S.: On hierarchical routing in doubling metrics. ACM Trans. Algorithms 12(4), 55:1-55:22 (2016). (12(4):55:1\u201355:22)","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"843_CR11","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1137\/130930984","volume":"44","author":"T-H Chan","year":"2015","unstructured":"Chan, T.-H., Li, M., Ning, L., Solomon, S.: New doubling spanners: better and simpler. SIAM J. Comput. 44(1), 37\u201353 (2015)","journal-title":"SIAM J. Comput."},{"key":"843_CR12","doi-asserted-by":"crossref","unstructured":"Das, Gautam., Heffernan, Paul J., Narasimhan, Giri.: Optimally sparse spanners in 3-dimensional euclidean space. In: Proceedings of the Ninth Annual Symposium on Computational GeometrySan Diego, CA, USA, May 19-21, 1993, pp. 53\u201362, 1993","DOI":"10.1145\/160985.160998"},{"key":"843_CR13","doi-asserted-by":"crossref","unstructured":"Elkin, Michael., Filtser, Arnold., Neiman, Ofer.: Prioritized metric structures and embedding. In: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14\u201317, 2015, pp. 489\u2013498, 2015","DOI":"10.1145\/2746539.2746623"},{"key":"843_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2017.06.021","volume":"697","author":"Michael Elkin","year":"2017","unstructured":"Elkin, Michael, Filtser, Arnold, Neiman, Ofer: Terminal embeddings. Theor. Comput. Sci. 697, 1\u201336 (2017)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"843_CR15","doi-asserted-by":"publisher","first-page":"35:1","DOI":"10.1145\/2819008","volume":"62","author":"M Elkin","year":"2015","unstructured":"Elkin, M., Solomon, S.: Optimal euclidean spanners: really short, thin, and lanky. J. ACM 62(5), 35:1-35:45 (2015)","journal-title":"J. ACM"},{"issue":"1\u20132","key":"843_CR16","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.comgeo.2005.10.001","volume":"35","author":"Jie Gao","year":"2006","unstructured":"Gao, Jie, Guibas, Leonidas J., Nguyen, An.: Deformable spanners and applications. Comput. Geom. Theory Appl. 35(1\u20132), 2\u201319 (2006)","journal-title":"Comput. Geom. Theory Appl."},{"key":"843_CR17","unstructured":"Gupta, Anupam., Krauthgamer, Robert., Lee, James R.: Bounded geometries, fractals, and low-distortion embeddings. In: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS \u201903, pp.534\u2013, Washington, DC, USA, 2003. IEEE Computer Society"},{"key":"843_CR18","doi-asserted-by":"crossref","unstructured":"Gottlieb, Lee-Ad.: a light metric spanner. In: Proc. of 56th FOCS, pp.759\u2013772, 2015","DOI":"10.1109\/FOCS.2015.52"},{"key":"843_CR19","doi-asserted-by":"crossref","unstructured":"Gottlieb, Lee-Ad., Roditty, Liam.: An optimal dynamic spanner for doubling metric spaces. In: Algorithms \u2014ESA 2008, 16th Annual European Symposium, Karlsruhe, Germany, September 15-17, 2008. Proceedings, pp. 478\u2013489, 2008","DOI":"10.1007\/978-3-540-87744-8_40"},{"issue":"5","key":"843_CR20","doi-asserted-by":"publisher","first-page":"1148","DOI":"10.1137\/S0097539704446281","volume":"35","author":"Sariel Har-Peled","year":"2006","unstructured":"Har-Peled, Sariel, Mendel, Manor: Fast construction of nets in low-dimensional metrics and their applications. SIAM J. Comput. 35(5), 1148\u20131184 (2006)","journal-title":"SIAM J. Comput."},{"key":"843_CR21","doi-asserted-by":"crossref","unstructured":"Johnson, William., Lindenstrauss, Joram.: Extensions of Lipschitz mappings into a Hilbert space. In: Conference in modern analysis and probability (New Haven, Conn., 1982), volume\u00a026 of Contemporary Mathematics, pp. 189\u2013206. American Mathematical Society, 1984","DOI":"10.1090\/conm\/026\/737400"},{"key":"843_CR22","unstructured":"Kavitha, Telikepalli.: New pairwise spanners. In: 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4-7, 2015, Garching, Germany, pp. 513\u2013526, 2015"},{"issue":"2","key":"843_CR23","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/BF01200757","volume":"15","author":"N Linial","year":"1995","unstructured":"Linial, N., London, E., Rabinovich, Y.: The geometry of graphs and some of its algorithmic applications. Combinatorica 15(2), 215\u2013245 (1995)","journal-title":"Combinatorica"},{"key":"843_CR24","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/BF02761110","volume":"93","author":"J Matou\u0161ek","year":"1996","unstructured":"Matou\u0161ek, J.: On the distortion required for embeding finite metric spaces into normed spaces. Israel J. Math. 93, 333\u2013344 (1996)","journal-title":"Israel J. Math."},{"key":"843_CR25","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0039-7","volume-title":"Lectures on Discrete Geometry","author":"Jiri Matousek","year":"2002","unstructured":"Matousek, Jiri: Lectures on Discrete Geometry. Springer, New York (2002)"},{"key":"843_CR26","doi-asserted-by":"crossref","unstructured":"Mahabadi,Sepideh., Makarychev, Konstantin., Makarychev, Yury., Razenshteyn, Ilya P.: Nonlinear dimension reduction via outer bi-lipschitz extensions. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pp. 1088\u20131101, 2018","DOI":"10.1145\/3188745.3188828"},{"issue":"2","key":"843_CR27","doi-asserted-by":"publisher","first-page":"253","DOI":"10.4171\/JEMS\/79","volume":"9","author":"Manor Mendel","year":"2007","unstructured":"Mendel, Manor, Naor, Assaf: Ramsey partitions and proximity data structures. J. Eur. Math. Soc. 9(2), 253\u2013275 (2007)","journal-title":"J. Eur. Math. Soc."},{"issue":"1","key":"843_CR28","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/s00224-014-9567-3","volume":"58","author":"Ofer Neiman","year":"2016","unstructured":"Neiman, Ofer: Low dimensional embeddings of doubling metrics. Theory Comput. Syst. 58(1), 133\u2013152 (2016)","journal-title":"Theory Comput. Syst."},{"key":"843_CR29","doi-asserted-by":"crossref","unstructured":"Narayanan, Shyam., Nelson, Jelani.: Optimal terminal dimensionality reduction in euclidean space. CoRR, abs\/1810.09250, 2018","DOI":"10.1145\/3313276.3316307"},{"key":"843_CR30","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546884","volume-title":"Geometric Spanner Networks","author":"Giri Narasimhan","year":"2007","unstructured":"Narasimhan, Giri, Smid, Michiel: Geometric Spanner Networks. Cambridge University Press, New York (2007)"},{"key":"843_CR31","doi-asserted-by":"crossref","unstructured":"Parter, Merav., Bypassing erd\u0151s\u2019 girth conjecture: Hybrid stretch and sourcewise spanners. In: Automata, Languages, and Programming\u201441st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8\u201311, 2014, Proceedings, Part II, pp. 608\u2013619, 2014","DOI":"10.1007\/978-3-662-43951-7_49"},{"issue":"2","key":"843_CR32","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0095-8956(91)90061-N","volume":"52","author":"N Robertson","year":"1991","unstructured":"Robertson, N., Seymour, P.D.: Graph minors: X. obstructions to tree-decomposition. J. Comb. Theory Ser. B 52(2), 153\u2013190 (1991)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"4","key":"843_CR33","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/s00446-006-0015-8","volume":"19","author":"Aleksandrs Slivkins","year":"2007","unstructured":"Slivkins, Aleksandrs: Distance estimation and object location via rings of neighbors. Distrib. Comput. 19(4), 313\u2013333 (2007)","journal-title":"Distrib. Comput."},{"key":"843_CR34","doi-asserted-by":"crossref","unstructured":"Talwar, Kunal.: Bypassing the embedding: Algorithms for low dimensional metrics. In: Proceedings of the Thirty-sixth Annual ACM Symposium on Theory of Computing, STOC \u201904, pp. 281\u2013290, New York, NY, USA, 2004. ACM","DOI":"10.1145\/1007352.1007399"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00843-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00843-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00843-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,27]],"date-time":"2021-10-27T12:03:02Z","timestamp":1635336182000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00843-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,26]]},"references-count":34,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2021,11]]}},"alternative-id":["843"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00843-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2021,7,26]]},"assertion":[{"value":"11 July 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 June 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 July 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}