{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:25:00Z","timestamp":1787340300860,"version":"build-2736575974"},"reference-count":31,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2012,1]]},"abstract":"<jats:p>Motivated by applications in combinatorial optimization, we study the extent to which the global properties of a metric space, and especially its embeddability into $\\ell_1$ with low distortion, are determined by the properties of its small subspaces. We establish both upper and lower bounds on the distortion of embedding locally constrained metrics into various target spaces. Other aspects of locally constrained metrics are studied as well, in particular, how far are those metrics from general metrics.<\/jats:p>","DOI":"10.1137\/090780304","type":"journal-article","created":{"date-parts":[[2012,2,9]],"date-time":"2012-02-09T18:40:01Z","timestamp":1328812801000},"page":"250-271","source":"Crossref","is-referenced-by-count":8,"title":["Local Versus Global Properties of Metric Spaces"],"prefix":"10.1137","volume":"41","author":[{"given":"Sanjeev","family":"Arora","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"L\u00e1szl\u00f3","family":"Lov\u00e1sz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ilan","family":"Newman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuval","family":"Rabani","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuri","family":"Rabinovich","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Santosh","family":"Vempala","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2012,2,9]]},"reference":[{"key":"R1","unstructured":"N. Alon and J. H. Spenser,\n                      The Probabilistic Method\n                      , 3rd ed., John Wiley and Sons, Hoboken, NJ, 2008."},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02189308"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a002"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-07-00573-5"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502794"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794285983"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2005.162.643"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/070712080"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1145\/1361192.1361199"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-006-0210-9"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480102417379"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"M.M. Deza and M. Laurent,\n                      Geometry of Cuts and Metrics\n                      , Springer-Verlag, Berlin, 1997.","DOI":"10.1007\/978-3-642-04295-9"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1990-0974513-6"},{"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                      , in Proceedings of the 35th Annual ACM Symposium on Theory of Computing, ACM, New York, 2004, pp. 60\u201370.","DOI":"10.1145\/992287.992300"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1007\/BF01188585"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"K. Georgiou, A. Magen, and I. Tourlakis,\n                      Vertex cover resists SDPs tightened by local hypermetric inequalities\n                      , in Integer Programming and Combinatorial Optimization, Lecture Notes in Comput. Sci. 5035, Springer, Berlin, 2008, pp. 140\u2013153.","DOI":"10.1007\/978-3-540-68891-4_10"},{"key":"R17","unstructured":"A. Gupta,\n                      Embeddings of Finite Metrics\n                      , Ph.D. thesis, University of California, Berkeley, CA, 2000."},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-004-0015-x"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.2307\/1970663"},{"key":"R21","unstructured":"W.B. Johnson and G. Schechtman,\n                      private communication\n                      , 2003."},{"key":"R22","doi-asserted-by":"crossref","unstructured":"S. Khot,\n                      On the power of unique 2-prover 1-round games\n                      , in Proceedings of the 34th Annual ACM Symposium on Theory of Computing, ACM, New York, 2002, pp. 767\u2013775.","DOI":"10.1145\/509907.510017"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2004.07.002"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200757"},{"key":"R25","first-page":"451","volume":"33","author":"Matousek J.","year":"1992","journal-title":"Comment. Math. Univ. Carolin."},{"key":"R26","unstructured":"J. Matousek,\n                      Open Problems on Embeddings of Finite Metric Spaces\n                      , http:\/\/kam.mff. cuni.cz\/~matousek\/metrop.ps."},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2008.168.247"},{"key":"R28","unstructured":"V. Milman and G. Schechtman,\n                      Asymptotic Theory of Finite-Dimensional Spaces\n                      , Lecture Notes in Math. 1200, Springer-Verlag, Berlin, 1986."},{"key":"R29","doi-asserted-by":"crossref","unstructured":"R. Motwani and P. Raghavan,\n                      Randomized Algorithms\n                      , Cambridge University Press, Cambridge, UK, 1995.","DOI":"10.1017\/CBO9780511814075"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009336"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.2307\/1968654"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/090780304","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:29:05Z","timestamp":1787336945000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/090780304"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.1137\/090780304"],"URL":"https:\/\/doi.org\/10.1137\/090780304","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1]]}}}