{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T05:35:39Z","timestamp":1740461739171,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642153686"},{"type":"electronic","value":"9783642153693"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15369-3_15","type":"book-chapter","created":{"date-parts":[[2010,8,27]],"date-time":"2010-08-27T04:01:36Z","timestamp":1282881696000},"page":"192-204","source":"Crossref","is-referenced-by-count":3,"title":["Proximity Algorithms for Nearly-Doubling Spaces"],"prefix":"10.1007","author":[{"given":"Lee-Ad","family":"Gottlieb","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert","family":"Krauthgamer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"doi-asserted-by":"crossref","unstructured":"Abraham, I., Bartal, Y., Neiman, O.: Local embeddings of metric spaces. In: Proceedings of 39th Annual ACM Symposium on Theory of Computing, pp. 631\u2013640 (2007)","key":"15_CR1","DOI":"10.1145\/1250790.1250883"},{"doi-asserted-by":"crossref","unstructured":"Abraham, I., Bartal, Y., Neiman, O.: Embedding metric spaces in their intrinsic dimension. In: 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 363\u2013372 (2008)","key":"15_CR2","DOI":"10.1145\/1250790.1250883"},{"unstructured":"Ackermann, M.R., Bl\u00f6mer, J., Sohler, C.: Clustering for metric and non-metric distance measures. In: SODA 2008: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 799\u2013808 (2008)","key":"15_CR3"},{"doi-asserted-by":"crossref","unstructured":"Abraham, I., Gavoille, C., Goldberg, A.V., Malkhi, D.: Routing in networks with low doubling dimension. In: 26th IEEE International Conference on Distributed Computing Systems, p.\u00a075 (2006)","key":"15_CR4","DOI":"10.1109\/ICDCS.2006.72"},{"issue":"4","key":"15_CR5","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 R n . Bull. Soc. Math. France\u00a0111(4), 429\u2013448 (1983)","journal-title":"Bull. Soc. Math. France"},{"unstructured":"Bartal, Y., Gottlieb, L., Kopelowitz, T., Lewenstein, M., Roditty, L.: Fast and precise distance queries (2010) (manuscript)","key":"15_CR6"},{"doi-asserted-by":"crossref","unstructured":"Beygelzimer, A., Kakade, S., Langford, J.: Cover trees for nearest neighbor. In: 23rd International Conference on Machine Learning, pp. 97\u2013104 (2006)","key":"15_CR7","DOI":"10.1145\/1143844.1143857"},{"issue":"6","key":"15_CR8","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1016\/j.jcss.2009.01.003","volume":"75","author":"N.H. Bshouty","year":"2009","unstructured":"Bshouty, N.H., Li, Y., Long, P.M.: Using the doubling dimension to analyze the generalization of learning algorithms. Journal of Computer and System Sciences\u00a075(6), 323\u2013335 (2009)","journal-title":"Journal of Computer and System Sciences"},{"unstructured":"Bartal, Y., Recht, B., Schulman, L.: A Nash-type dimensionality reduction for discrete subsets of L 2. Manuscript (2007), http:\/\/www.ist.caltech.edu\/~brecht\/publications.html","key":"15_CR9"},{"doi-asserted-by":"crossref","unstructured":"Chan, T.-H., Gupta, A.: Small hop-diameter sparse spanners for doubling metrics. In: 17th Annual ACM-SIAM Symposium on Discrete Algorithm, pp. 70\u201378 (2006)","key":"15_CR10","DOI":"10.1145\/1109557.1109566"},{"doi-asserted-by":"crossref","unstructured":"Cole, R., Gottlieb, L.: Searching dynamic point sets in spaces with bounded doubling dimension. In: 38th Annual ACM Symposium on Theory of Computing, pp. 574\u2013583 (2006)","key":"15_CR11","DOI":"10.1145\/1132516.1132599"},{"unstructured":"Chan, T.-H.H., Gupta, A.: Approximating tsp on metrics with bounded global growth. In: SODA 2008: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 690\u2013699 (2008)","key":"15_CR12"},{"unstructured":"Chan, H., Gupta, A., Talwar, K.: Ultra-low-dimensional embeddings for doubling metrics. In: 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 333\u2013342 (2008)","key":"15_CR13"},{"issue":"1-2","key":"15_CR14","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/S0304-3975(97)00226-0","volume":"225","author":"A.E.F. Clementi","year":"1999","unstructured":"Clementi, A.E.F.: Improved non-approximability results for minimum vertex cover with density constraints. Theor. Comput. Sci.\u00a0225(1-2), 113\u2013128 (1999)","journal-title":"Theor. Comput. Sci."},{"key":"15_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/11945529_12","volume-title":"Principles of Distributed Systems","author":"M. Damian","year":"2006","unstructured":"Damian, M., Pandit, S., Pemmaraju, S.V.: Distributed spanner construction in doubling metric spaces. In: Shvartsman, M.M.A.A. (ed.) OPODIS 2006. LNCS, vol.\u00a04305, pp. 157\u2013171. Springer, Heidelberg (2006)"},{"issue":"6-7","key":"15_CR16","doi-asserted-by":"crossref","first-page":"572","DOI":"10.1016\/j.comgeo.2010.01.001","volume":"43","author":"S.A. Friedler","year":"2010","unstructured":"Friedler, S.A., Mount, D.M.: Approximation algorithm for the kinetic robust k-center problem. Comput. Geom. Theory Appl.\u00a043(6-7), 572\u2013586 (2010)","journal-title":"Comput. Geom. Theory Appl."},{"issue":"1","key":"15_CR17","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/j.comgeo.2005.10.001","volume":"35","author":"J. Gao","year":"2006","unstructured":"Gao, J., Guibas, L.J., Nguyen, A.: Deformable spanners and applications. Comput. Geom. Theory Appl.\u00a035(1), 2\u201319 (2006)","journal-title":"Comput. Geom. Theory Appl."},{"doi-asserted-by":"crossref","unstructured":"Gionis, A., Hinneburg, A., Papadimitriou, S., Tsaparas, P.: Dimension induced clustering. In: KDD 2005: Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, pp. 51\u201360 (2005)","key":"15_CR18","DOI":"10.1145\/1081870.1081880"},{"unstructured":"Gottlieb, L., Krauthgamer, R.: A nonlinear approach to dimension reduction. In: CoRR, abs\/0907.5477 (2009)","key":"15_CR19"},{"unstructured":"Gottlieb, L., Kontorovich, A., Krauthgamer, R.: Efficient classification for metric data. In: COLT (2010)","key":"15_CR20"},{"doi-asserted-by":"crossref","unstructured":"Gupta, A., Krauthgamer, R., Lee, J.R.: Bounded geometries, fractals, and low-distortion embeddings. In: 44th Annual IEEE Symposium on Foundations of Computer Science, pp. 534\u2013543 (October 2003)","key":"15_CR21","DOI":"10.1109\/SFCS.2003.1238226"},{"unstructured":"Gottlieb, L., Roditty, L.: Improved algorithms for fully dynamic geometric spanners and geometric routing. In: SODA 2008: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 591\u2013600 (2008)","key":"15_CR22"},{"key":"15_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"478","DOI":"10.1007\/978-3-540-87744-8_40","volume-title":"ESA 2008","author":"L. Gottlieb","year":"2008","unstructured":"Gottlieb, L., Roditty, L.: An optimal dynamic spanner for doubling metric spaces. In: Halperin, D., Mehlhorn, K. (eds.) Esa 2008. LNCS, vol.\u00a05193, pp. 478\u2013489. Springer, Heidelberg (2008)"},{"doi-asserted-by":"crossref","unstructured":"Hastad, J.: Clique is hard to approximate within n 1\u2009\u2212\u2009\u03b5 . Acta Mathematica, 627\u2013636 (1996)","key":"15_CR24","DOI":"10.1109\/SFCS.1996.548522"},{"key":"15_CR25","first-page":"150","volume-title":"21st Annual Symposium on Computational Geometry","author":"S. Har-Peled","year":"2005","unstructured":"Har-Peled, S., Mendel, M.: Fast construction of nets in low dimensional metrics, and their applications. In: 21st Annual Symposium on Computational Geometry, pp. 150\u2013158. ACM, New York (2005)"},{"issue":"5","key":"15_CR26","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"},{"unstructured":"Krauthgamer, R., Lee, J.R.: Navigating nets: Simple algorithms for proximity search. In: 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 791\u2013801 (January 2004)","key":"15_CR27"},{"key":"15_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/978-3-540-87779-0_26","volume-title":"Distributed Computing","author":"G. Konjevod","year":"2008","unstructured":"Konjevod, G., Richa, A.W., Xia, D.: Dynamic routing and location services in metrics of low doubling dimension. In: Taubenfeld, G. (ed.) DISC 2008. LNCS, vol.\u00a05218, pp. 379\u2013393. Springer, Heidelberg (2008)"},{"key":"15_CR29","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1145\/1281100.1281113","volume-title":"26th Annual ACM Symposium on Principles of Distributed Computing","author":"G. Konjevod","year":"2007","unstructured":"Konjevod, G., Richa, A.W., Xia, D., Yu, H.: Compact routing with slack in low doubling dimension. In: 26th Annual ACM Symposium on Principles of Distributed Computing, pp. 71\u201380. ACM, New York (2007)"},{"doi-asserted-by":"crossref","unstructured":"Kleinberg, J.M., Slivkins, A., Wexler, T.: Triangulation and embedding using small sets of beacons. In: 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 444\u2013453 (2004)","key":"15_CR30","DOI":"10.1109\/FOCS.2004.70"},{"issue":"3","key":"15_CR31","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C.H. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. System Sci.\u00a043(3), 425\u2013440 (1991)","journal-title":"J. Comput. System Sci."},{"doi-asserted-by":"crossref","unstructured":"Slivkins, A.: Distance estimation and object location via rings of neighbors. In: Proceedings of the 24th Annual ACM Symposium on Principles of Distributed Computing, pp. 41\u201350 (2005)","key":"15_CR32","DOI":"10.1145\/1073814.1073823"},{"doi-asserted-by":"crossref","unstructured":"Talwar, K.: Bypassing the embedding: Algorithms for low dimensional metrics. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pp. 281\u2013290 (2004)","key":"15_CR33","DOI":"10.1145\/1007352.1007399"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15369-3_15.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T03:48:23Z","timestamp":1740455303000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15369-3_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642153686","9783642153693"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15369-3_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}