{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T08:09:19Z","timestamp":1787386159489,"version":"build-2736575974"},"reference-count":26,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>Suppose that every k points in a n point metric space X are D-distortion embeddable into $\\ell_1$. We give upper and lower bounds on the distortion required to embed the entire space X into $\\ell_1$. This is a natural mathematical question and is also motivated by the study of relaxations obtained by lift-and-project methods for graph partitioning problems. In this setting, we show that X can be embedded into $\\ell_1$ with distortion $O(D\\times\\log(n\/k))$. Moreover, we give a lower bound showing that this result is tight if D is bounded away from 1. For $D=1+\\delta$ we give a lower bound of $\\Omega(\\log(n\/k)\/\\log(1\/\\delta))$; and for $D=1$, we give a lower bound of $\\Omega(\\log n\/(\\log k+\\log\\log n))$. Our bounds significantly improve on the results of Arora et al. who initiated a study of these questions.<\/jats:p>","DOI":"10.1137\/070712080","type":"journal-article","created":{"date-parts":[[2010,4,30]],"date-time":"2010-04-30T18:31:20Z","timestamp":1272652280000},"page":"2487-2512","source":"Crossref","is-referenced-by-count":11,"title":["Local Global Tradeoffs in Metric Embeddings"],"prefix":"10.1137","volume":"39","author":[{"given":"Moses","family":"Charikar","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Konstantin","family":"Makarychev","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yury","family":"Makarychev","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,4,30]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"I. Abraham, M. Balakrishnan, F. Kuhn, D. Malkhi, V. Ramasubramanian, and K. Talwar,\n                      Reconstructing approximate tree metrics\n                      , Proceedings of the 26th Annual ACM Symposium on Principles of Distributed Computing, ACM, New York, 2007, pp. 43\u201352.","DOI":"10.1145\/1281100.1281110"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"I. Abraham, Y. Bartal, and O. Neiman,\n                      Local embeddings of metric spaces\n                      , Proceedings of the 39th Annual ACM Symposium on Theory of Computing, ACM, New York, 2007, pp. 631\u2013640.","DOI":"10.1145\/1250790.1250883"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a002"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"S. Arora, J. Lee, and A. Naor,\n                      Euclidean distortion and the sparsest cut\n                      , Proceedings of the 37th Annual ACM Symposium on Theory of Computing, ACM, New York, 2005, pp. 553\u2013562.","DOI":"10.1145\/1060590.1060673"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"S. Arora, L. Lov\u00e1sz, I. Newman, Y. Rabani, Y. Rabinovich, and S. Vempala,\n                      Local versus global properties of metric spaces\n                      , Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, SIAM, Philadelphia, 2006, pp. 41\u201350.","DOI":"10.1145\/1109557.1109563"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"S. Arora, S. Rao, and U. Vazirani,\n                      Expander flows, geometric embeddings and graph partitioning\n                      , Proceedings of the 36th Annual ACM Symposium on Theory of Computing, ACM, New York, 2004, pp. 222\u2013231.","DOI":"10.1145\/1007352.1007355"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794285983"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1007\/BF02776078"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1007\/BF02766125"},{"key":"R10","unstructured":"G. Calinescu, H. Karloff, and Y. Rabani,\n                      Approximation algorithms for the\n                      0\n                      -extension problem\n                      , Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2001, pp. 8\u201316."},{"key":"R11","doi-asserted-by":"crossref","unstructured":"H. Chan, M. Dinitz, and A. Gupta,\n                      Spanners with slack\n                      , Lecture Notes in Comput. Sci. 4168, Springer, Berlin, 2006, pp. 196\u2013207.","DOI":"10.1007\/11841036_20"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"M. Charikar, K. Makarychev, and Y. Makarychev,\n                      Integrality gaps for Sherali\u2013Adams relaxations\n                      , Proceedings of the 41st Annual ACM Symposium on Theory of Computing, ACM, New York, 2009, pp. 293\u2013302.","DOI":"10.1145\/1536414.1536455"},{"key":"R13","unstructured":"W. F. de la Vega and C. Kenyon-Mathieu,\n                      Linear programming relaxations of Maxcut\n                      , Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, SIAM, Philadelphia, 2007, pp. 53\u201361."},{"key":"R14","doi-asserted-by":"crossref","unstructured":"J. Fakcharoenphol, S. Rao, and K. Talwar,\n                      A tight bound on approximating arbitrary metrics by tree metrics\n                      , Proceedings of the 35th Annual ACM Symposium on Theory of Computing, ACM, New York, 2003, pp. 448\u2013455.","DOI":"10.1145\/780542.780608"},{"key":"R15","first-page":"175","volume":"32","author":"Helly E.","year":"1923","journal-title":"Jber. Deutsch. Math. Vereinig"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200757"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2004.07.002"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1137\/0801013"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1007\/BF02773799"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1007\/BF02785579"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"J. Matou\u0161ek,\n                      Lectures on Discrete Geometry\n                      , Grad. Texts in Math. 212, Springer-Verlag, New York, 2002.","DOI":"10.1007\/978-1-4613-0039-7"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2003.12.001"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1007\/BF01448840"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1137\/0403036"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"G. Schoenebeck, L. Trevisan, and M. Tulsiani,\n                      Tight integrality gaps for Lov\u00e1sz-Schrijver LP relaxations of vertex cover and max cut\n                      , Proceedings of the 39th Annual Symposium on ACM Symposium on Theory of Computing, ACM, New York, 2007, pp. 302\u2013310.","DOI":"10.1145\/1250790.1250836"},{"key":"R26","unstructured":"N. Tomczak-Jaegermann,\n                      Banach\u2013Mazur Distances and Finite-Dimensional Operator Ideals\n                      , Pitman Monogr. Surveys Pure Appl. Math. 38, Longman Scientific & Technical, Harlow, UK, 1989."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/070712080","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:36:50Z","timestamp":1787337410000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/070712080"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":26,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/070712080"],"URL":"https:\/\/doi.org\/10.1137\/070712080","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}