{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:05:18Z","timestamp":1750694718619,"version":"3.40.4"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,9,5]],"date-time":"2014-09-05T00:00:00Z","timestamp":1409875200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2016,1]]},"DOI":"10.1007\/s00224-014-9567-3","type":"journal-article","created":{"date-parts":[[2014,9,4]],"date-time":"2014-09-04T12:40:56Z","timestamp":1409834456000},"page":"133-152","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Low Dimensional Embeddings of Doubling Metrics"],"prefix":"10.1007","volume":"58","author":[{"given":"Ofer","family":"Neiman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,9,5]]},"reference":[{"key":"9567_CR1","first-page":"363","volume-title":"Embedding metric spaces in their intrinsic dimension. In: Proceedings of the 19th annual ACM-SIAM symposium on Discrete algorithms, SODA \u201908","author":"I Abraham","year":"2008","unstructured":"Abraham, I., Bartal, Y., Neiman, O.: Embedding metric spaces in their intrinsic dimension. In: Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201908, pp. 363\u2013372. Society for Industrial and Applied Mathematics, Philadelphia (2008)"},{"issue":"4","key":"9567_CR2","doi-asserted-by":"crossref","first-page":"429","DOI":"10.24033\/bsmf.1997","volume":"111","author":"P Assouad","year":"1983","unstructured":"Assouad, P.: Plongements lipschitziens dans \u211d n . Bull. Soc. Math. France 111(4), 429\u2013448 (1983)","journal-title":"Bull. Soc. Math. France"},{"issue":"5","key":"9567_CR3","doi-asserted-by":"crossref","first-page":"766","DOI":"10.1145\/1089023.1089026","volume":"52","author":"B Bo","year":"2005","unstructured":"Bo, B., Charikar, M.: On the impossibility of dimension reduction in l1. J. ACM 52(5), 766\u2013788 (2005)","journal-title":"J. ACM"},{"key":"9567_CR4","first-page":"663","volume-title":"The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme. In: Proceedings of the 44th symposium on Theory of Computing, STOC \u201912","author":"Y Bartal","year":"2012","unstructured":"Bartal, Y., Gottlieb, L.-A., Krauthgamer, R.: The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme. In: Proceedings of the 44th symposium on Theory of Computing, STOC \u201912, pp 663\u2013672. ACM, New York (2012)"},{"key":"9567_CR5","volume-title":"Extremal graph theory","author":"B Bollob\u00e1s","year":"1978","unstructured":"Bollob\u00e1s, B.: Extremal graph theory. Academic Press Inc. [Harcourt Brace Jovanovich Publishers], London (1978)"},{"key":"9567_CR6","doi-asserted-by":"crossref","unstructured":"Bartal, Y., Recht, B., Schulman, L.J.: Dimensionality reduction: beyond the johnson-lindenstrauss bound. In: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201911, pp. 868\u2013887. SIAM (2011)","DOI":"10.1137\/1.9781611973082.68"},{"key":"9567_CR7","unstructured":"Hubert Chan, T-H., Gupta, A., Maggs, B.M., Zhou, S.: On hierarchical routing in doubling metrics. In: Proceedings 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2005)"},{"key":"9567_CR8","doi-asserted-by":"crossref","unstructured":"Hubert Chan, T.-H., Gupta, A., Talwar, K.: Ultra-low-dimensional embeddings for doubling metrics. J. ACM 57(4) (2010)","DOI":"10.1145\/1734213.1734215"},{"issue":"2","key":"9567_CR9","doi-asserted-by":"crossref","first-page":"1347","DOI":"10.4007\/annals.2010.171.1347","volume":"171","author":"J Cheeger","year":"2010","unstructured":"Cheeger, J., Kleiner, B.: Differentiating maps into L 1, and the geometry of BV functions. Annals of Math. 171(2), 1347\u20131385 (2010)","journal-title":"Annals of Math."},{"key":"9567_CR10","doi-asserted-by":"crossref","unstructured":"Cheeger, J., Kleiner, B., Assaf Naor, A.: (logn)\u03a9(1) integrality gap for the sparsest cut sdp. In: Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS \u201909, pp 555\u2013564. IEEE Computer Society, Washington (2009)","DOI":"10.1109\/FOCS.2009.47"},{"key":"9567_CR11","doi-asserted-by":"crossref","unstructured":"Gottlieb, L.-A., Krauthgamer, R.: A nonlinear approach to dimension reduction. In: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201911, pp. 888\u2013899. SIAM (2011)","DOI":"10.1137\/1.9781611973082.69"},{"key":"9567_CR12","doi-asserted-by":"crossref","unstructured":"Gupta, A., Krauthgamer, R., Lee, J.R.: Bounded geometries, fractals, and lowdistortion embeddings. In: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 03, pp. 534\u2013543. IEEE Computer Society,Washington, DC (2003)","DOI":"10.1109\/SFCS.2003.1238226"},{"key":"9567_CR13","unstructured":"Gottlieb, L.-A., Roditty, L.: Improved algorithms for fully dynamic geometric spanners and geometric routing. In: Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 08, pp. 591\u2013600. Society for Industrial and Applied Mathematics, Philadelphia (2008)"},{"issue":"5","key":"9567_CR14","doi-asserted-by":"crossref","first-page":"1148","DOI":"10.1137\/S0097539704446281","volume":"35","author":"S Har-Peled","year":"2006","unstructured":"Har-Peled, S., Mendel, M.: 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":"9567_CR15","doi-asserted-by":"crossref","unstructured":"Jaffe, A., Lee, J.R., Moharrami, M.: On the optimality of gluing over scales. In: Proceedings of the 12th International Workshop and 13th International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX \u201909 \/ RANDOM \u201909, pp. 190\u2013201,Berlin, Springer-Verlag, Heidelberg (2009)","DOI":"10.1007\/978-3-642-03685-9_15"},{"issue":"4","key":"9567_CR16","doi-asserted-by":"crossref","first-page":"839","DOI":"10.1007\/s00039-005-0527-6","volume":"15","author":"R Krauthgamer","year":"2005","unstructured":"Krauthgamer, R., Lee, J.R., Mendel, M., Naor, A.: Measured descent: a new embedding method for finite metrics. Geom. Funct. Anal. 15(4), 839\u2013858 (2005)","journal-title":"Geom. Funct. Anal."},{"key":"9567_CR17","doi-asserted-by":"crossref","unstructured":"Laakso, T.J.: Plane with A \u221e -weighted metric not bi-Lipschitz embeddable to \u211d N . Bull. London Math. Soc. 34(6), 667\u2013676 (2002)","DOI":"10.1112\/S0024609302001200"},{"issue":"2","key":"9567_CR18","doi-asserted-by":"crossref","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"},{"issue":"8","key":"9567_CR19","doi-asserted-by":"crossref","first-page":"1180","DOI":"10.1016\/j.ejc.2004.07.002","volume":"26","author":"JR Lee","year":"2005","unstructured":"Lee, J.R., Mendel, M., Naor, A.: Metric structures in l1: dimension, snowflakes, and average distortion. Eur. J. Comb. 26(8), 1180\u20131190 (2005)","journal-title":"Eur. J. Comb."},{"key":"9567_CR20","unstructured":"Lee, J.R., Naor, A.: Embedding the diamond graph in l p and dimension reduction in l 1, 745\u2013747 (2004)"},{"issue":"1\u20133","key":"9567_CR21","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1023\/A:1012093209450","volume":"87","author":"U Lang","year":"2001","unstructured":"Lang, U., Plaut, C.: Bilipschitz embeddings of metric spaces into space form. Geometriae Dedicata 87(1\u20133), 285\u2013307 (2001)","journal-title":"Geometriae Dedicata"},{"key":"9567_CR22","doi-asserted-by":"crossref","unstructured":"Lee, J.R.: Anastasios Sidiropoulos. Near-optimal distortion bounds for embedding doubling spaces into l1. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, STOC \u201911, pp. 765\u2013772. ACM, New York (2011)","DOI":"10.1145\/1993636.1993737"},{"key":"9567_CR23","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0039-7","volume-title":"Lectures on discrete geometry","author":"J Matous\u0307ek","year":"2002","unstructured":"Matous\u0307ek, J.: Lectures on discrete geometry. Springer-Verlag, New York (2002)"},{"issue":"4,","key":"9567_CR24","doi-asserted-by":"crossref","first-page":"1","DOI":"10.4171\/RMI\/706","volume":"28","author":"A Naor","year":"2012","unstructured":"Naor, A., Neiman, O.: Assouad\u2019s theorem with dimension independent of the snowflaking. Revista Matematica Iberoamericana 28(4), 1\u201321 (2012)","journal-title":"Revista Matematica Iberoamericana"},{"key":"9567_CR25","doi-asserted-by":"crossref","unstructured":"Semmes, S.: On the nonexistence of bilipschitz parameterizations and geometric problems about a \u221e weights. Revista Matem\u00e1tica Iberoamericana 12, 337\u2013410 (1996)","DOI":"10.4171\/RMI\/201"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9567-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-014-9567-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9567-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,4]],"date-time":"2025-05-04T13:14:08Z","timestamp":1746364448000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-014-9567-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,9,5]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["9567"],"URL":"https:\/\/doi.org\/10.1007\/s00224-014-9567-3","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2014,9,5]]}}}