{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:39:46Z","timestamp":1787337586011,"version":"build-2736575974"},"reference-count":44,"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":[[2009,1]]},"abstract":"<jats:p>We consider the problem of embedding finite metrics with slack: We seek to produce embeddings with small dimension and distortion while allowing a (small) constant fraction of all distances to be arbitrarily distorted. This definition is motivated by recent research in the networking community, which achieved striking empirical success at embedding Internet latencies with low distortion into low-dimensional Euclidean space, provided that some small slack is allowed. Answering an open question of Kleinberg, Slivkins, and Wexler [in Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, 2004], we show that provable guarantees of this type can in fact be achieved in general: Any finite metric space can be embedded, with constant slack and constant distortion, into constant-dimensional Euclidean space. We then show that there exist stronger embeddings into $\\ell_1$ which exhibit gracefully degrading distortion: There is a single embedding into $\\ell_1$ that achieves distortion at most $O(\\log\\frac{1}{\\epsilon})$ on all but at most-1.5pt an $\\epsilon$ fraction of distances simultaneously for all $\\epsilon&gt;0$. We extend this with distortion1pt $O(\\log\\frac{1}{\\epsilon})^{1\/p}$ to maps into general $\\ell_p$, $p\\geq1$, for several classes of metrics, including those with bounded doubling dimension and those arising from the shortest-path metric of a graph with an excluded minor. Finally, we show that many of our constructions are tight and give a general technique to obtain lower bounds for $\\epsilon$-slack embeddings from lower bounds for low-distortion embeddings.<\/jats:p>","DOI":"10.1137\/060670511","type":"journal-article","created":{"date-parts":[[2009,3,4]],"date-time":"2009-03-04T19:30:36Z","timestamp":1236195036000},"page":"2303-2329","source":"Crossref","is-referenced-by-count":8,"title":["Metric Embeddings with Relaxed Guarantees"],"prefix":"10.1137","volume":"38","author":[{"given":"T.-H. Hubert","family":"Chan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kedar","family":"Dhamdhere","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anupam","family":"Gupta","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jon","family":"Kleinberg","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aleksandrs","family":"Slivkins","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2009,3,4]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"I. Abraham, Y. Bartal, T.H. H. Chan, K. Dhamdhere, A. Gupta, J. Kleinberg, O. Neiman, and A. Slivkins,\n                      Metric embeddings with relaxed guarantees\n                      , in Proceedings of the 46th IEEE Symposium on Foundations of Computer Science (FOCS), Pittsburgh, PA, 2005, pp. 83\u2013100.","DOI":"10.1109\/SFCS.2005.51"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"I. Abraham, Y. Bartal, and O. Neiman,\n                      Advances in metric embedding theory\n                      , in Proceedings of the 38th ACM Symposium on Theory of Computing (STOC), Seattle, WA, 2006.","DOI":"10.1145\/1132516.1132557"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792224474"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.24033\/bsmf.1997"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"Y. Bartal,\n                      Probabilistic approximations of metric spaces and its algorithmic applications\n                      , in Proceedings of the 37th IEEE Symposium on Foundations of Computer Science (FOCS), Burlington, VT, 1996, pp. 184\u2013193.","DOI":"10.1109\/SFCS.1996.548477"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"Y. Bartal,\n                      On approximating arbitrary metrics by tree metrics\n                      , in Proceedings of the 30th ACM Symposium on Theory of Computing (STOC), Dallas, TX, 1998, pp. 161\u2013168.","DOI":"10.1145\/276698.276725"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"Y. Bartal,\n                      Graph decomposition lemmas and their role in metric embedding methods\n                      , in Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms (SODA), Bergen, Norway, 2004, pp. 89\u201397.","DOI":"10.1007\/978-3-540-30140-0_10"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"Y. Bartal, B. Bollob\u00e1s, and M. Mendel,\n                      Ramsey-type theorems for metric spaces with applications to online problems\n                      , J. Comput. System Sci., 72 (2002), pp. 890\u2013921. Preliminary version in\n                      $42$nd IEEE FOCS\n                      , 2001.","DOI":"10.1016\/j.jcss.2005.05.008"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"Y. Bartal, N. Linial, M. Mendel, and A. Naor,\n                      On metric Ramsey-type phenomena\n                      , Ann. of Math., 162 (2005), pp. 643\u2013709. Preliminary version in\n                      $35$th ACM STOC\n                      , 2003.","DOI":"10.4007\/annals.2005.162.643"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1007\/BF02776078"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1007\/BF02801990"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1145\/1089023.1089026"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"F. Dabek, R. Cox, F. Kaashoek, and R. Morris,\n                      Vivaldi: A decentralized network coordinate system\n                      , in Proceedings of the ACM Special Interest Group on Data Communications (SIGCOMM), Portland, OR, 2004.","DOI":"10.1145\/1015467.1015471"},{"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                      , J. Comput. System Sci., 69 (2004), pp. 485\u2013497. Preliminary version in\n                      $35$th ACM STOC\n                      , 2003.","DOI":"10.1016\/j.jcss.2004.04.011"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"J. Fakcharoenphol and K. Talwar,\n                      An improved decomposition theorem for graphs excluding a fixed minor\n                      , in Proceedings of the RANDOM-APPROX, Princeton, NJ, Springer-Verlag, 2003, pp. 36\u201346.","DOI":"10.1007\/978-3-540-45198-3_4"},{"key":"R16","unstructured":"M. Fomenkov, L. Claffy, B. Huffaker, and D. Moore,\n                      Macroscopic internet topology and performance measurements from the DNS root name servers\n                      , in Proceedings of the Usenix Large Installation System Administration (LISA) Conference, San Diego, CA, 2001."},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1109\/90.958323"},{"key":"R18","unstructured":"A. Gupta,\n                      Steiner points in tree metrics don't (really) help\n                      , in Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms (SODA), Philadelphia, 2001, pp. 220\u2013227."},{"key":"R19","doi-asserted-by":"crossref","unstructured":"A. Gupta, R. Krauthgamer, and J. R. Lee,\n                      Bounded geometries, fractals, and low\u2013distortion embeddings\n                      , in Proceedings of the 44th IEEE Symposium on Foundations of Computer Science (FOCS), Cambridge, MA, 2003, pp. 534\u2013543.","DOI":"10.1109\/SFCS.2003.1238226"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-004-0015-x"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"J. D. Guyton and M, F. Schwartz,\n                      Locating nearby copies of replicated Internet servers\n                      , in Proceedings of the ACM Special Interest Group on Data Communications (SIGCOMM), Cambridge, MA, 1995.","DOI":"10.21236\/ADA451456"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446281"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"J. Heinonen,\n                      Lectures on Analysis on Metric Spaces\n                      , Universitext, Springer-Verlag, New York, 2001.","DOI":"10.1007\/978-1-4613-0131-8"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"P. Indyk,\n                      Algorithmic applications of low-distortion geometric embeddings\n                      , in Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science (FOCS), Los Vegas, NV, 2001, pp. 10\u201333.","DOI":"10.1109\/SFCS.2001.959878"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"P. Indyk and J. Matou\u0161ek,\n                      Low-distortion embeddings of finite metric spaces\n                      , in Handbook of Discrete and Computational Geometry, 2nd ed., J. E. Goodman and J. O'Rourke, eds., Discrete Math. Appl. (Boca Raton), Chapman & Hall\/CRC, Boca Raton, FL, 2004, pp. 177\u2013196.","DOI":"10.1201\/9781420035315.ch8"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"D. R. Karger and M. Ruhl,\n                      Finding nearest neighbors in growth-restricted metrics\n                      , in Proceedings of the 34th ACM Symposium on Theory of Computing (STOC), Montreal, Canada, 2002, pp. 63\u201366.","DOI":"10.1145\/510008.510013"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"P. Klein, S. A. Plotkin, and S. B. Rao,\n                      Excluded minors, network decomposition, and multicommodity flow\n                      , in Proceedings of the 25th ACM Symposium on Theory of Computing (STOC), 1993, San Diego, CA, pp. 682\u2013690.","DOI":"10.1145\/167088.167261"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"J. Kleinberg, A. Slivkins, and T. Wexler,\n                      Triangulation and embedding using small sets of beacons\n                      , in Proceedings of the 45th IEEE Symposium on Foundations of Computer Science (FOCS), Rome, Italy, 2004, pp. 444\u2013453.","DOI":"10.1109\/FOCS.2004.70"},{"key":"R29","unstructured":"C. Kommareddy, N. Shankar, and B. Bhattacharjee,\n                      Finding close friends on the Internet\n                      , in Proceedings of the 12th IEEE International Conference on Network Protocols (ICNP), Berlin, Germany, 2001."},{"key":"R30","doi-asserted-by":"crossref","unstructured":"R. Krauthgamer, J. Lee, M. Mendel, and A. Naor,\n                      Measured descent: A new embedding method for finite metrics\n                      , Geom. Funct. Anal., 15 (2005), pp. 839\u2013858. Preliminary version in\n                      $45$th IEEE FOCS\n                      , 2004.","DOI":"10.1007\/s00039-005-0527-6"},{"key":"R31","unstructured":"J. R. Lee,\n                      On distance scales, embeddings, and efficient relaxations of the cut cone\n                      , in Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA), Vancouver, Canada, 2005, pp. 92\u2013101."},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2004.07.002"},{"key":"R33","doi-asserted-by":"crossref","unstructured":"N. Linial, E. London, and Y. Rabinovich,\n                      The geometry of graphs and some of its algorithmic applications\n                      , Combinatorica, 15 (1995), pp. 215\u2013245. Preliminary version in\n                      $35$th IEEE FOCS\n                      , 1994.","DOI":"10.1007\/BF01200757"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1007\/BF02773799"},{"key":"R35","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":"R36","first-page":"589","volume":"31","author":"Matou\u0161ek J.","year":"1990","journal-title":"Comment. Math. Univ. Carolin."},{"key":"R37","unstructured":"T. S. E. Ng and H. Zhang,\n                      Predicting Internet network distance with coordinates-based approaches\n                      , in Proceedings of the 21st Joint Conference of the IEEE Computer and Communication (INFOCOM), New York, 2002."},{"key":"R38","unstructured":"T. S. E. Ng and H. Zhang,\n                      A network positioning system for the Internet\n                      , in Proceedings of the USENIX, Boston, 2004."},{"key":"R39","doi-asserted-by":"crossref","unstructured":"C. G. Plaxton, R. Rajaraman, and A. W. Richa,\n                      Accessing nearby copies of replicated objects in a distributed environment\n                      , Theory Comput. Syst., 32 (1999), pp. 241\u2013280. Preliminary version in\n                      9th ACM SPAA\n                      , 1997.","DOI":"10.1007\/s002240000118"},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009336"},{"key":"R41","doi-asserted-by":"crossref","unstructured":"S. B. Rao,\n                      Small distortion and volume preserving embeddings for planar and Euclidean metrics\n                      , in Proceedings of the 15th ACM Symposium on Computational Geometry (SoCG), Miami, FL, 1999, pp. 300\u2013306.","DOI":"10.1145\/304893.304983"},{"key":"R42","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2004.838597"},{"key":"R43","unstructured":"A. Slivkins,\n                      Distributed approaches to triangulation and embedding\n                      , in Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA), Vancouver, Canada, 2005, pp. 640\u2013649."},{"key":"R44","doi-asserted-by":"crossref","unstructured":"K. Talwar,\n                      Bypassing the embedding: Algorithms for low-dimensional metrics\n                      , in Proceedings of the 36th ACM Symposium on Theory of Computing (STOC), Chicago, IL, 2004, pp. 281\u2013290.","DOI":"10.1145\/1007352.1007399"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/060670511","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:19:09Z","timestamp":1787336349000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/060670511"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1]]},"references-count":44,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2009,1]]}},"alternative-id":["10.1137\/060670511"],"URL":"https:\/\/doi.org\/10.1137\/060670511","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1]]}}}