{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T11:39:13Z","timestamp":1725795553933},"publisher-location":"Cham","reference-count":24,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319080000"},{"type":"electronic","value":"9783319080017"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-08001-7_2","type":"book-chapter","created":{"date-parts":[[2014,6,10]],"date-time":"2014-06-10T16:53:00Z","timestamp":1402419180000},"page":"12-23","source":"Crossref","is-referenced-by-count":0,"title":["Low Dimensional Embeddings of Doubling Metrics"],"prefix":"10.1007","author":[{"given":"Ofer","family":"Neiman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"2_CR1","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 2008, Philadelphia, PA, USA, pp. 363\u2013372. Society for Industrial and Applied Mathematics (2008)"},{"issue":"4","key":"2_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\u00a0111(4), 429\u2013448 (1983)","journal-title":"Bull. Soc. Math. France"},{"issue":"5","key":"2_CR3","doi-asserted-by":"publisher","first-page":"766","DOI":"10.1145\/1089023.1089026","volume":"52","author":"B. Brinkman","year":"2005","unstructured":"Brinkman, B., Charikar, M.: On the impossibility of dimension reduction in l1. J. ACM\u00a052(5), 766\u2013788 (2005)","journal-title":"J. ACM"},{"key":"2_CR4","doi-asserted-by":"crossref","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 2012, New York, NY, USA, pp. 663\u2013672. ACM (2012)","DOI":"10.1145\/2213977.2214038"},{"key":"2_CR5","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 2011, pp. 868\u2013887. SIAM (2011)","DOI":"10.1137\/1.9781611973082.68"},{"key":"2_CR6","unstructured":"Chan, T.-H.H., Gupta, A., Maggs, B.M., Zhou, S.: On hierarchical routing in doubling metrics. In: Proc. 16th Ann. ACM-SIAM Symposium on Discrete Algorithms, SODA (2005)"},{"key":"2_CR7","doi-asserted-by":"crossref","unstructured":"Chan, T.-H.H., Gupta, A., Talwar, K.: Ultra-low-dimensional embeddings for doubling metrics. J. ACM\u00a057(4) (2010)","DOI":"10.1145\/1734213.1734215"},{"issue":"2","key":"2_CR8","doi-asserted-by":"publisher","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\u00a0171(2), 1347\u20131385 (2010)","journal-title":"Annals of Math"},{"key":"2_CR9","doi-asserted-by":"crossref","unstructured":"Cheeger, J., Kleiner, B., Naor, A.: 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 2009, Washington, DC, USA, pp. 555\u2013564. IEEE Computer Society (2009)","DOI":"10.1109\/FOCS.2009.47"},{"key":"2_CR10","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 2011, pp. 888\u2013899. SIAM (2011)","DOI":"10.1137\/1.9781611973082.69"},{"key":"2_CR11","doi-asserted-by":"crossref","unstructured":"Gupta, A., Krauthgamer, R., Lee, J.R.: Bounded geometries, fractals, and low-distortion embeddings. In: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003, Washington, DC, USA, pp. 534\u2013543. IEEE Computer Society (2003)","DOI":"10.1109\/SFCS.2003.1238226"},{"key":"2_CR12","unstructured":"Gottlieb, L.-A., Roditty, L.: Improved algorithms for fully dynamic geometric spanners and geometric routing. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, Philadelphia, PA, USA, pp. 591\u2013600. Society for Industrial and Applied Mathematics (2008)"},{"issue":"5","key":"2_CR13","doi-asserted-by":"publisher","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 Journal on Computing\u00a035(5), 1148\u20131184 (2006)","journal-title":"SIAM Journal on Computing"},{"key":"2_CR14","doi-asserted-by":"crossref","unstructured":"Jaffe, A., Lee, J.R., Moharrami, M.: On the optimality of gluing over scales. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX and RANDOM 2009. LNCS, vol.\u00a05687, pp. 190\u2013201. Springer, Heidelberg (2009)","DOI":"10.1007\/978-3-642-03685-9_15"},{"issue":"4","key":"2_CR15","doi-asserted-by":"publisher","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. Geometric and Functional Analysis\u00a015(4), 839\u2013858 (2005)","journal-title":"Geometric and Functional Analysis"},{"issue":"6","key":"2_CR16","doi-asserted-by":"publisher","first-page":"667","DOI":"10.1112\/S0024609302001200","volume":"34","author":"T.J. Laakso","year":"2002","unstructured":"Laakso, T.J.: Plane with A \u2009\u221e\u2009-weighted metric not bi-Lipschitz embeddable to ${\\Bbb R}^N$ . Bull. London Math. Soc.\u00a034(6), 667\u2013676 (2002)","journal-title":"Bull. London Math. Soc."},{"issue":"2","key":"2_CR17","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\u00a015(2), 215\u2013245 (1995)","journal-title":"Combinatorica"},{"issue":"8","key":"2_CR18","doi-asserted-by":"publisher","first-page":"1180","DOI":"10.1016\/j.ejc.2004.07.002","volume":"26","author":"J.R. Lee","year":"2005","unstructured":"Lee, J.R., Mendel, M., Naor, A.: Metric structures in l1: dimension, snowflakes, and average distortion. Eur. J. Comb.\u00a026(8), 1180\u20131190 (2005)","journal-title":"Eur. J. Comb."},{"key":"2_CR19","doi-asserted-by":"crossref","unstructured":"Lee, J.R., Naor, A.: Embedding the diamond graph in l p and dimension reduction in l 1, pp. 745\u2013747 (2004)","DOI":"10.1007\/s00039-004-0473-8"},{"issue":"1-3","key":"2_CR20","doi-asserted-by":"publisher","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\u00a087(1-3), 285\u2013307 (2001)","journal-title":"Geometriae Dedicata"},{"key":"2_CR21","doi-asserted-by":"crossref","unstructured":"Lee, J.R., Sidiropoulos, A.: Near-optimal distortion bounds for embedding doubling spaces into l1. In: Proceedings of the 43rd annual ACM symposium on Theory of computing, STOC 2011, New York, NY, USA, pp. 765\u2013772. ACM (2011)","DOI":"10.1145\/1993636.1993737"},{"key":"2_CR22","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0039-7","volume-title":"Lectures on discrete geometry","author":"J. Matou\u0161ek","year":"2002","unstructured":"Matou\u0161ek, J.: Lectures on discrete geometry. Springer, New York (2002)"},{"issue":"4","key":"2_CR23","doi-asserted-by":"publisher","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\u00a028(4), 1\u201321 (2012)","journal-title":"Revista Matematica Iberoamericana"},{"key":"2_CR24","doi-asserted-by":"publisher","first-page":"337","DOI":"10.4171\/RMI\/201","volume":"12","author":"S. Semmes","year":"1996","unstructured":"Semmes, S.: On the nonexistence of bilipschitz parameterizations and geometric problems about a \u2009\u221e\u2009 weights. Revista Matem\u00e1tica Iberoamericana\u00a012, 337\u2013410 (1996)","journal-title":"Revista Matem\u00e1tica Iberoamericana"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-08001-7_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,11]],"date-time":"2019-08-11T11:30:00Z","timestamp":1565523000000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-08001-7_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319080000","9783319080017"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-08001-7_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}