{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T17:05:29Z","timestamp":1787504729478,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540282396","type":"print"},{"value":"9783540318743","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11538462_10","type":"book-chapter","created":{"date-parts":[[2010,9,28]],"date-time":"2010-09-28T00:13:22Z","timestamp":1285632802000},"page":"111-122","source":"Crossref","is-referenced-by-count":9,"title":["Approximating the Distortion"],"prefix":"10.1007","author":[{"given":"Alexander","family":"Hall","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christos","family":"Papadimitriou","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"10_CR1","doi-asserted-by":"crossref","unstructured":"Kenyon, C., Rabani, Y., Sinclair, A.: Low distortion maps between point sets. In: Proceedings of the 36th STOC, pp. 272\u2013280 (2004)","DOI":"10.1145\/1007352.1007398"},{"key":"10_CR2","unstructured":"Papadimitriou, C., Safra, S.: The complexity of low-distortion embeddings between point sets. In: Proceedings of the 16th SODA, pp. 112\u2013118 (2005)"},{"key":"10_CR3","doi-asserted-by":"crossref","unstructured":"Indyk, P.: Algorithmic applications of low-distortion geometric embeddings. In: Tutorial at the 42nd FOCS, pp. 10\u201333 (2001)","DOI":"10.1109\/SFCS.2001.959878"},{"key":"10_CR4","doi-asserted-by":"crossref","unstructured":"Linial, N.: Finite metric spaces \u2013 combinatorics, geometry and algorithms. In: Proceedings of the International Congress of Mathematicians III, Beijing, pp. 573\u2013586 (2002)","DOI":"10.1145\/513400.513441"},{"key":"10_CR5","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0039-7","volume-title":"Lectures on Discrete Geometry","author":"J. Matousek","year":"2002","unstructured":"Matousek, J.: Lectures on Discrete Geometry. Graduate Texts in Mathematics, vol.\u00a0212. Springer, Heidelberg (2002)"},{"key":"10_CR6","unstructured":"Web-page of the working group on multi-dimensional scaling (2005), http:\/\/dimacs.rutgers.edu\/SpecialYears\/2001_Data\/Algorithms\/AlgorithmsMS.htm"},{"key":"10_CR7","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, 215\u2013245 (1995)","journal-title":"Combinatorica"},{"key":"10_CR8","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 into hilbert space. Isreal Journal of Mathematics\u00a052, 46\u201352 (1985)","journal-title":"Isreal Journal of Mathematics"},{"key":"10_CR9","doi-asserted-by":"crossref","unstructured":"Kleinberg, J., Slivkins, A., Wexler, T.: Triangulation and embedding using small sets of beacons. In: Proceedings of the 45th FOCS, pp. 444\u2013453 (2004)","DOI":"10.1109\/FOCS.2004.70"},{"key":"10_CR10","unstructured":"Slivkins, A.: Distributed approaches to triangulation and embedding. In: Proceedings of the 16th SODA, pp. 640\u2013649 (2005)"},{"key":"10_CR11","unstructured":"B\u02d8adoiu, M., Dhamdhere, K., Gupta, A., Rabinovich, Y., R\u00e4cke, H., Ravi, R., Sidiropoulos, A.: Approximation algorithms for low-distortion embeddings into low-dimensional spaces. In: Proceedings of the 16th SODA, pp. 119\u2013128 (2005)"},{"key":"10_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/3-540-68530-8_39","volume-title":"Algorithms - ESA \u201998","author":"J. H\u00e5stad","year":"1998","unstructured":"H\u00e5stad, J., Ivansson, L., Lagergren, J.: Fitting points on the real line and its application to RH mapping. In: Bilardi, G., Pietracaprina, A., Italiano, G.F., Pucci, G. (eds.) ESA 1998. LNCS, vol.\u00a01461, pp. 465\u2013467. Springer, Heidelberg (1998)"},{"key":"10_CR13","unstructured":"B\u0103doiu, M.: Approximation algorithm for embedding metrics into a twodimensional space. In: Proceedings of the 14th SODA, pp. 434\u2013443 (2003)"},{"key":"10_CR14","unstructured":"B\u0103doiu, M., Indyk, P., Rabinovich, Y.: Approximate algorithms for embedding metrics into low dimensional spaces (2003) (manuscript)"},{"key":"10_CR15","doi-asserted-by":"publisher","first-page":"510","DOI":"10.1006\/jcss.1999.1682","volume":"60","author":"U. Feige","year":"2000","unstructured":"Feige, U.: Approximating the bandwidth via volume respecting embeddings. Journal of Computer and System Sciences\u00a060, 510\u2013539 (2000)","journal-title":"Journal of Computer and System Sciences"},{"key":"10_CR16","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1016\/S0166-218X(02)00282-2","volume":"127","author":"T. Akutsu","year":"2003","unstructured":"Akutsu, T., Kanaya, K., Ohyama, A., Fujiyama, A.: Point matching under nonuniform distortions. Discrete Applied Mathematics\u00a0127, 5\u201321 (2003)","journal-title":"Discrete Applied Mathematics"}],"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\/11538462_10.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T15:13:43Z","timestamp":1605626023000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11538462_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540282396","9783540318743"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/11538462_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005]]}}}