{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:33:53Z","timestamp":1750221233372,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":48,"publisher":"ACM","license":[{"start":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T00:00:00Z","timestamp":1529452800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ISF","award":["1817\/17"],"award-info":[{"award-number":["1817\/17"]}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1536002, CCF-1540541, CCF-1617790"],"award-info":[{"award-number":["CCF-1536002, CCF-1540541, CCF-1617790"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"BSF","award":["2015813"],"award-info":[{"award-number":["2015813"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2018,6,20]]},"DOI":"10.1145\/3188745.3188808","type":"proceedings-article","created":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T20:15:46Z","timestamp":1529525746000},"page":"952-963","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Metric embedding via shortest path decompositions"],"prefix":"10.1145","author":[{"given":"Ittai","family":"Abraham","sequence":"first","affiliation":[{"name":"VMware, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arnold","family":"Filtser","sequence":"additional","affiliation":[{"name":"Ben-Gurion University of the Negev, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anupam","family":"Gupta","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ofer","family":"Neiman","sequence":"additional","affiliation":[{"name":"Ben-Gurion University of the Negev, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,6,20]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2011.08.003"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"crossref","unstructured":"1016\/j.aim.2011.08.003  1016\/j.aim.2011.08.003","DOI":"10.1088\/1475-7516\/2011\/08\/003"},{"volume-title":"APPROX\/RANDOM 2015","year":"2015","author":"Abraham Ittai","key":"e_1_3_2_2_3_1"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146411"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591849"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90026-2"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.24033\/bsmf.1997"},{"key":"e_1_3_2_2_8_1","unstructured":"Nikhil Bansal Niv Buchbinder Aleksander Madry and Joseph Naor. 2011.  Nikhil Bansal Niv Buchbinder Aleksander Madry and Joseph Naor. 2011."},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.63"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.05.038"},{"key":"e_1_3_2_2_11_1","unstructured":"Hans L. Bodlaender John R. Gilbert Hj\u00e1lmt\u00fdr Hafsteinsson and Ton Kloks. 1992.  Hans L. Bodlaender John R. Gilbert Hj\u00e1lmt\u00fdr Hafsteinsson and Ton Kloks. 1992."},{"volume-title":"pathwidth, and minimum elimination tree height","author":"Approximating","key":"e_1_3_2_2_12_1"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02776078"},{"key":"e_1_3_2_2_14_1","unstructured":"N. L. Carothers. 2004.  N. L. Carothers. 2004."},{"key":"e_1_3_2_2_15_1","unstructured":"A Short Course on Banach Space Theory. Cambridge University Press.  A Short Course on Banach Space Theory. Cambridge University Press."},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.79"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480102417379"},{"volume-title":"Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society","author":"Gupta Anupam","key":"e_1_3_2_2_18_1"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702409927"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-004-0015-x"},{"volume-title":"On the Non-Uniform Sparsest Cut Problem on Bounded Treewidth Graphs. In Annual ACM Symposium on Theory of Computing. 281\u2013290","year":"2013","author":"Gupta Anupam","key":"e_1_3_2_2_21_1"},{"volume-title":"On the Optimality of Gluing over Scales. Discrete &amp","year":"2011","author":"Jaffe Alexander","key":"e_1_3_2_2_22_1"},{"volume-title":"Johnson and Gideon Schechtman","year":"2009","author":"William","key":"e_1_3_2_2_23_1"},{"volume-title":"Journal of Topology and Analysis 01, 02","year":"2009","author":"DIAMOND GRAPHS AND","key":"e_1_3_2_2_24_1"},{"key":"e_1_3_2_2_25_1","unstructured":"Lior Kamma and Robert Krauthgamer. 2016.  Lior Kamma and Robert Krauthgamer. 2016."},{"volume-title":"1\u20139. s00453- 016- 0213- 0","year":"2016","author":"Path-Separable Graphs Metric Decompositions","key":"e_1_3_2_2_26_1"},{"key":"e_1_3_2_2_27_1","unstructured":"Maleq Khan Fabian Kuhn Dahlia Malkhi Gopal Pandurangan and Kunal Talwar. 2012.  Maleq Khan Fabian Kuhn Dahlia Malkhi Gopal Pandurangan and Kunal Talwar. 2012."},{"volume-title":"Distributed Computing 25, 3","year":"2012","author":"Efficient","key":"e_1_3_2_2_28_1"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-005-0527-6"},{"volume-title":"Lee and Assaf Naor","year":"2004","author":"James","key":"e_1_3_2_2_30_1"},{"volume-title":"Lee and Prasad Raghavendra","year":"2010","author":"James","key":"e_1_3_2_2_31_1"},{"volume-title":"Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010","year":"2010","author":"James","key":"e_1_3_2_2_32_1"},{"volume-title":"Lee and Anastasios Sidiropoulos","year":"2013","author":"James","key":"e_1_3_2_2_33_1"},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-013-2685-8"},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200757"},{"key":"e_1_3_2_2_36_1","unstructured":"Manor Mendel and Assaf Naor. 2013.  Manor Mendel and Assaf Naor. 2013."},{"volume-title":"Journal of the European Mathematical Society 15, 1","year":"2013","author":"Markov","key":"e_1_3_2_2_37_1"},{"key":"e_1_3_2_2_38_1","unstructured":"Gary L. Miller. 1986.  Gary L. Miller. 1986."},{"volume-title":"265\u2013279. 0022- 0000(86)90030- 9","year":"1986","author":"Simple Cycle Finding Small","key":"e_1_3_2_2_39_1"},{"key":"e_1_3_2_2_40_1","unstructured":"Ilan Newman and Yuri Rabinovich. 2003.  Ilan Newman and Yuri Rabinovich. 2003."},{"volume-title":"Discrete Comput. Geom. 29, 1","year":"2003","author":"A","key":"e_1_3_2_2_41_1"},{"key":"e_1_3_2_2_42_1","unstructured":"Haruko Okamura and P.D. Seymour. 1981.  Haruko Okamura and P.D. Seymour. 1981."},{"key":"e_1_3_2_2_43_1","series-title":"Series B 31, 1","volume-title":"Journal of Combinatorial Theory","author":"Multicommodity","year":"1981"},{"key":"e_1_3_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/304893.304983"},{"key":"e_1_3_2_2_45_1","unstructured":"Yuval Shavitt and Tomer Tankel. 2004.  Yuval Shavitt and Tomer Tankel. 2004."},{"key":"e_1_3_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2004.838597"},{"key":"e_1_3_2_2_47_1","unstructured":"Mikkel Thorup. 2004.  Mikkel Thorup. 2004."},{"key":"e_1_3_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039493"}],"event":{"name":"STOC '18: Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Los Angeles CA USA","acronym":"STOC '18"},"container-title":["Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188808","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3188745.3188808","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3188745.3188808","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:07:09Z","timestamp":1750212429000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188808"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,20]]},"references-count":48,"alternative-id":["10.1145\/3188745.3188808","10.1145\/3188745"],"URL":"https:\/\/doi.org\/10.1145\/3188745.3188808","relation":{},"subject":[],"published":{"date-parts":[[2018,6,20]]},"assertion":[{"value":"2018-06-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}