{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T06:31:31Z","timestamp":1725517891632},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540853626"},{"type":"electronic","value":"9783540853633"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-85363-3_3","type":"book-chapter","created":{"date-parts":[[2008,8,27]],"date-time":"2008-08-27T19:29:28Z","timestamp":1219865368000},"page":"21-34","source":"Crossref","is-referenced-by-count":5,"title":["Ordinal Embedding: Approximation Algorithms and Dimensionality Reduction"],"prefix":"10.1007","author":[{"given":"Mihai","family":"B\u0103doiu","sequence":"first","affiliation":[]},{"given":"Erik D.","family":"Demaine","sequence":"additional","affiliation":[]},{"given":"MohammadTaghi","family":"Hajiaghayi","sequence":"additional","affiliation":[]},{"given":"Anastasios","family":"Sidiropoulos","sequence":"additional","affiliation":[]},{"given":"Morteza","family":"Zadimoghaddam","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"3_CR1","unstructured":"Alon, N., B\u0103doiu, M., Demaine, E.D., Farach-Colton, M., Hajiaghayi, M., Sidiropoulos, A.: Ordinal embeddings of minimum relaxation: General properties, trees, and ultrametrics. ACM Transactions on Algorithms (to appear)"},{"key":"3_CR2","doi-asserted-by":"crossref","unstructured":"Alon, N., Frankl, P., R\u00f6dl, V.: Geometrical realization of set systems and probabilistic communication complexity. In: Proceedings of the 26th Annual Symposium on Foundations of Computer Science, pp. 277\u2013280. Portland, Oregon (1985)","DOI":"10.1109\/SFCS.1985.30"},{"issue":"5","key":"3_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 $l\\sb 1$ . Journal of the ACM (electronic)\u00a052(5), 766\u2013788 (2005)","journal-title":"Journal of the ACM (electronic)"},{"key":"3_CR4","volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"M. B\u0103doiu","year":"2005","unstructured":"B\u0103doiu, M., Dhamdhere, K., Gupta, A., Rabinovich, Y., Raecke, H., Ravi, R., Sidiropoulos, A.: Approximation algorithms for low-distortion embeddings into low-dimensional spaces. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, Vancouver, January 2005, British Columbia, Canada (2005)"},{"key":"3_CR5","unstructured":"B\u0103doiu, M., Indyk, P., Sidiropoulos, A.: Approximation algorithms for embedding general metrics into trees. In: Proceedings of the 18th Symposium on Discrete Algorithms, January 2007, pp. 512\u2013521 (2007)"},{"key":"3_CR6","unstructured":"Bilu, Y., Linial, N.: Monotone maps, sphericity and bounded second eigenvalue. arXiv:math.CO\/0401293 (January 2004)"},{"key":"3_CR7","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/0022-2496(74)90027-3","volume":"11","author":"J.P. Cunningham","year":"1974","unstructured":"Cunningham, J.P., Shepard, R.N.: Monotone mapping of similarities into a general metric space. Journal of Mathematical Psychology\u00a011, 335\u2013364 (1974)","journal-title":"Journal of Mathematical Psychology"},{"issue":"4","key":"3_CR8","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1137\/S0895480195296221","volume":"11","author":"B. Chor","year":"1998","unstructured":"Chor, B., Sudan, M.: A geometric approach to betweennes. SIAM Journal on Discrete Mathematics\u00a011(4), 511\u2013523 (1998)","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"1-2","key":"3_CR9","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/BF02392234","volume":"139","author":"T. Figiel","year":"1977","unstructured":"Figiel, T., Lindenstrauss, J., Milman, V.D.: The dimension of almost spherical sections of convex bodies. Acta Mathematica\u00a0139(1-2), 53\u201394 (1977)","journal-title":"Acta Mathematica"},{"key":"3_CR10","first-page":"177","volume-title":"Handbook of Discrete and Computational Geometry","author":"P. Indyk","year":"2004","unstructured":"Indyk, P., Matou\u0161ek, J.: Low-distortion embeddings of finite metric spaces. In: Goodman, J.E., O\u2019Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, 2nd edn., ch.\u00a08, pp. 177\u2013196. CRC Press, Boca Raton (2004)","edition":"2"},{"key":"3_CR11","doi-asserted-by":"crossref","unstructured":"Indyk, P.: Uncertainty principles, extractors, and explicit embeddings of l2 into l1. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pp. 615\u2013620 (2007)","DOI":"10.1145\/1250790.1250881"},{"key":"3_CR12","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1090\/conm\/026\/737400","volume":"26","author":"W.B. Johnson","year":"1984","unstructured":"Johnson, W.B., Lindenstrauss, J.: Extensions of lipshitz mapping into hilbert space. Contemporary Mathematics\u00a026, 189\u2013206 (1984)","journal-title":"Contemporary Mathematics"},{"issue":"4","key":"3_CR13","doi-asserted-by":"publisher","first-page":"845","DOI":"10.1007\/s00039-003-0432-9","volume":"13","author":"W.B. Johnson","year":"2003","unstructured":"Johnson, W.B., Schechtman, G.: Very tight embeddings of subspaces of L p , 1\u2009\u2264\u2009p\u2009<\u20092, into $\\ell^n_p$ . Geometric and Functional Analysis\u00a013(4), 845\u2013851 (2003)","journal-title":"Geometric and Functional Analysis"},{"key":"3_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02289565","volume":"29","author":"J.B. Kruskal","year":"1964","unstructured":"Kruskal, J.B.: Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis. Psychometrika\u00a029, 1\u201328 (1964)","journal-title":"Psychometrika"},{"key":"3_CR15","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/BF02289694","volume":"29","author":"J.B. Kruskal","year":"1964","unstructured":"Kruskal, J.B.: Non-metric multidimensional scaling. Psychometrika\u00a029, 115\u2013129 (1964)","journal-title":"Psychometrika"},{"issue":"4","key":"3_CR16","doi-asserted-by":"publisher","first-page":"745","DOI":"10.1007\/s00039-004-0473-8","volume":"14","author":"J.R. Lee","year":"2004","unstructured":"Lee, J.R., Naor, A.: Embedding the diamond graph in L p and dimension reduction in L 1. Geometric and Functional Analysis\u00a014(4), 745\u2013747 (2004)","journal-title":"Geometric and Functional Analysis"},{"issue":"2","key":"3_CR17","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1016\/j.aim.2003.12.001","volume":"189","author":"M. Mendel","year":"2004","unstructured":"Mendel, M., Naor, A.: Euclidean quotients of finite metric spaces. Advances in Mathematics\u00a0189(2), 451\u2013494 (2004)","journal-title":"Advances in Mathematics"},{"key":"3_CR18","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1137\/0208008","volume":"8","author":"J. Opatrny","year":"1979","unstructured":"Opatrny, J.: Total ordering problem. SIAM J. Computing\u00a08, 111\u2013114 (1979)","journal-title":"SIAM J. Computing"},{"issue":"3","key":"3_CR19","doi-asserted-by":"publisher","first-page":"522","DOI":"10.2307\/1989894","volume":"44","author":"I.J. Schoenberg","year":"1938","unstructured":"Schoenberg, I.J.: Metric spaces and positive definite functions. Transactions of the American Mathematical Society\u00a044(3), 522\u2013536 (1938)","journal-title":"Transactions of the American Mathematical Society"},{"key":"3_CR20","unstructured":"Shah, R., Farach-Colton, M.: On the complexity of ordinal clustering. Journal of Classification (to appear, 2004)"},{"key":"3_CR21","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/BF02289630","volume":"27","author":"R.N. Shepard","year":"1962","unstructured":"Shepard, R.N.: Multidimensional scaling with unknown distance function I. Psychometrika\u00a027, 125\u2013140 (1962)","journal-title":"Psychometrika"},{"issue":"4","key":"3_CR22","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/BF02288916","volume":"17","author":"W.S. Torgerson","year":"1952","unstructured":"Torgerson, W.S.: Multidimensional scaling I: Theory and method. Psychometrika\u00a017(4), 401\u2013414 (1952)","journal-title":"Psychometrika"},{"key":"3_CR23","volume-title":"Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 84","author":"J.H. Wells","year":"1975","unstructured":"Wells, J.H., Williams, L.R.: Embeddings and extensions in analysis. In: Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 84, Springer-Verlag, New York (1975)"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-85363-3_3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:24:19Z","timestamp":1606184659000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-85363-3_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540853626","9783540853633"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-85363-3_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}