{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,8]],"date-time":"2025-03-08T15:40:06Z","timestamp":1741448406977,"version":"3.38.0"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642229343"},{"type":"electronic","value":"9783642229350"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22935-0_5","type":"book-chapter","created":{"date-parts":[[2011,8,12]],"date-time":"2011-08-12T09:20:39Z","timestamp":1313140839000},"page":"50-61","source":"Crossref","is-referenced-by-count":0,"title":["Bandwidth and Low Dimensional Embedding"],"prefix":"10.1007","author":[{"given":"Yair","family":"Bartal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Douglas E.","family":"Carroll","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adam","family":"Meyerson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ofer","family":"Neiman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"5_CR1","unstructured":"Abraham, I., Bartal, Y., Neiman, O.: Embedding metric spaces in their intrinsic dimension. In: SODA 2008: Proceedings of the 18th Ann. ACM-SIAM Sym. on Discrete Algorithms (2008)"},{"issue":"4","key":"5_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"},{"key":"5_CR3","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1002\/rsa.3240020402","volume":"2","author":"J. Beck","year":"1991","unstructured":"Beck, J.: An algorithmic approach to the lov\u00e1sz local lemma. Random Struct. Algorithms\u00a02, 343\u2013365 (1991)","journal-title":"Random Struct. Algorithms"},{"issue":"1-2","key":"5_CR4","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 in Hilbert space. Israel J. Math.\u00a052(1-2), 46\u201352 (1985)","journal-title":"Israel J. Math."},{"issue":"2","key":"5_CR5","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1007\/BF02766125","volume":"56","author":"J. Bourgain","year":"1986","unstructured":"Bourgain, J.: The metrical interpretation of superreflexivity in Banach spaces. Israel J. Math.\u00a056(2), 222\u2013230 (1986)","journal-title":"Israel J. Math."},{"key":"5_CR6","doi-asserted-by":"crossref","unstructured":"Brinkman, B., Charikar, M.: On the impossibility of dimension reduction in l $_{\\mbox{1}}$ . In: FOCS, pp. 514\u2013523 (2003)","DOI":"10.1109\/SFCS.2003.1238224"},{"key":"5_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/11786986_4","volume-title":"Automata, Languages and Programming","author":"D.E. Carroll","year":"2006","unstructured":"Carroll, D.E., Goel, A., Meyerson, A.: Embedding bounded bandwidth graphs into \u21131. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol.\u00a04051, pp. 27\u201337. Springer, Heidelberg (2006)"},{"key":"5_CR8","doi-asserted-by":"crossref","unstructured":"Chakrabarti, A., Jaffe, A., Lee, J.R., Vincent, J.: Embeddings of topological graphs: Lossy invariants, linearization, and 2-sums. In: Proceedings of the 49th Ann. IEEE Sym. on Foundations of Computer Science, Washington, DC, USA, pp. 761\u2013770 (2008)","DOI":"10.1109\/FOCS.2008.79"},{"key":"5_CR9","unstructured":"Chekuri, C., Gupta, A., Newman, I., Rabinovich, Y., Sinclair, A.: Embedding k-outerplanar graphs into \u21131. In: SODA 2003: Proceedings of the 14th Ann. ACM-SIAM Sym. on Discrete Algorithms, pp. 527\u2013536 (2003)"},{"key":"5_CR10","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1002\/jgt.3190060302","volume":"6","author":"P.Z. Chinn","year":"1982","unstructured":"Chinn, P.Z., Chv\u00e1talov\u00e1, J., Dewdney, A.K., Gibbs, N.E.: The bandwidth problem for graphs and matrices - a survey. Journal of Graph Theory\u00a0(6), 223\u2013254 (1982)","journal-title":"Journal of Graph Theory"},{"key":"5_CR11","first-page":"90","volume-title":"Proceedings of the 30th Ann. ACM Sym. on Theory of Computing, STOC 1998","author":"U. Feige","year":"1998","unstructured":"Feige, U.: Approximating the bandwidth via volume respecting embeddings. In: Proceedings of the 30th Ann. ACM Sym. on Theory of Computing, STOC 1998, pp. 90\u201399. ACM, New York (1998)"},{"key":"5_CR12","doi-asserted-by":"crossref","unstructured":"Gupta, A., Krauthgamer, R., Lee, J.s.R.: Bounded geometries, fractals, and low-distortion embeddings. In: Proceedings of the 44th Ann. IEEE Sym. on Foundations of Computer Science, Washington, DC, USA, p. 534 (2003)","DOI":"10.1109\/SFCS.2003.1238226"},{"key":"5_CR13","doi-asserted-by":"crossref","unstructured":"Gupta, A., Newman, I., Rabinovich, Y., Sinclair, A.: Cuts, trees and \u21131-embeddings of graphs. In: Proceedings of the 40th Ann. Sym. on Foundations of Computer Science, pp. 399\u2013409 (1999)","DOI":"10.1109\/SFFCS.1999.814611"},{"issue":"2","key":"5_CR14","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"},{"key":"5_CR15","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/BF02785579","volume":"114","author":"J. Matousek","year":"1999","unstructured":"Matousek, J.: On embedding trees into uniformly convex banach spaces. Israel Journal of Mathematics\u00a0114, 221\u2013237 (1999)","journal-title":"Israel Journal of Mathematics"},{"issue":"2","key":"5_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1667053.1667060","volume":"57","author":"R.A. Moser","year":"2010","unstructured":"Moser, R.A., Tardos, G.: A constructive proof of the general lov\u00e1sz local lemma. J. ACM\u00a057(2), 1\u201315 (2010)","journal-title":"J. ACM"},{"key":"5_CR17","first-page":"94","volume-title":"SCG 2002: Proceedings of the 18th ann. sym. on Computational geometry","author":"I. Newman","year":"2002","unstructured":"Newman, I., Rabinovich, Y.: A lower bound on the distortion of embedding planar metrics into euclidean space. In: SCG 2002: Proceedings of the 18th ann. sym. on Computational geometry, pp. 94\u201396. ACM Press, New York (2002)"},{"key":"5_CR18","first-page":"300","volume-title":"Proceedings of the 15th Ann. Sym. on Computational Geometry","author":"S. Rao","year":"1999","unstructured":"Rao, S.: Small distortion and volume preserving embeddings for planar and Euclidean metrics. In: Proceedings of the 15th Ann. Sym. on Computational Geometry, pp. 300\u2013306. ACM, New York (1999)"},{"key":"5_CR19","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"},{"issue":"2","key":"5_CR20","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1109\/TCBB.2008.121","volume":"6","author":"Q. Zhu","year":"2009","unstructured":"Zhu, Q., Adam, Z., Choi, V., Sankoff, D.: Generalized gene adjacencies, graph bandwidth, and clusters in yeast evolution. IEEE\/ACM Trans. Comput. Biol. Bioinformatics\u00a06(2), 213\u2013220 (2009)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinformatics"}],"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-22935-0_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,8]],"date-time":"2025-03-08T15:18:17Z","timestamp":1741447097000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22935-0_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642229343","9783642229350"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22935-0_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}