{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:42:37Z","timestamp":1787341357262,"version":"build-2736575974"},"reference-count":38,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/501100001824","name":"Czech Science Foundation","doi-asserted-by":"crossref","award":["P202\/12\/G061"],"award-info":[{"award-number":["P202\/12\/G061"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100021797","name":"Hausdorff Research Institute for Mathematics","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100021797","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Research Institute for Discrete Mathematics in Bonn, Germany"},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>Graphs with bounded highway dimension were introduced by Abraham et al. [ Proceedings of SODA 2010, pp. 782--793] as a model of transportation networks. We show that any such graph can be embedded into a distribution over bounded treewidth graphs with arbitrarily small distortion. More concretely, given a weighted graph $G=(V,E)$ of constant highway dimension, we show how to randomly compute a weighted graph $H=(V,E')$ that distorts shortest path distances of $G$ by at most a $1+\\varepsilon$ factor in expectation, and whose treewidth is polylogarithmic in the aspect ratio of $G$. Our probabilistic embedding implies quasi-polynomial time approximation schemes for a number of optimization problems that naturally arise in transportation networks, including Travelling Salesman, Steiner Tree, and Facility Location. To construct our embedding for low highway dimension graphs we extend Talwar's [ Proceedings of STOC 2004, pp. 281--290] embedding of low doubling dimension metrics into bounded treewidth graphs, which generalizes known results for Euclidean metrics. We add several nontrivial ingredients to Talwar's techniques, and in particular thoroughly analyze the structure of low highway dimension graphs. Thus we demonstrate that the geometric toolkit used for Euclidean metrics extends beyond the class of low doubling metrics.<\/jats:p>","DOI":"10.1137\/16m1067196","type":"journal-article","created":{"date-parts":[[2018,8,21]],"date-time":"2018-08-21T14:27:46Z","timestamp":1534861666000},"page":"1667-1704","source":"Crossref","is-referenced-by-count":17,"title":["A $(1+\\varepsilon)$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs"],"prefix":"10.1137","volume":"47","author":[{"given":"Andreas Emil","family":"Feldmann","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wai Shing","family":"Fung","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jochen","family":"K\u00f6nemann","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ian","family":"Post","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,8,21]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"I. Abraham, A. Fiat, A. V. Goldberg, and R. F. Werneck,\n                      Highway dimension, shortest paths, and provably efficient algorithms\n                      , in Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, 2010, pp. 782-793,https:\/\/doi.org\/10.1137\/1.9781611973075.64.","DOI":"10.1137\/1.9781611973075.64"},{"key":"atypb2","first-page":"690","author":"Abraham I.","year":"2011","journal-title":"New York"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"I. Abraham, C. Gavoille, A. Gupta, O. Neiman, and K. Talwar,\n                      Cops, robbers, and threatening skeletons: Padded decomposition for minor-free graphs\n                      , in Proceedings of the 46th Annual ACM Symposium on Theory of Computing, 2014, pp. 79-88,https:\/\/doi.org\/10.1145\/2591796.2591849.","DOI":"10.1145\/2591796.2591849"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1145\/2985473"},{"key":"atypb6","first-page":"237","author":"Ageev A. A.","year":"1992","journal-title":"PA"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290180"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-003-0438-y"},{"key":"atypb9","first-page":"106","author":"Arora S.","year":"1998","journal-title":"New York"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"S. Arora,\n                      Polynomial time approximation schemes for Euclidean TSP and other geometric problems\n                      , in Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, 1996, pp. 2-11,https:\/\/doi.org\/10.1109\/SFCS.1996.548458.","DOI":"10.1109\/SFCS.1996.548458"},{"key":"atypb11","first-page":"184","author":"Bartal Y.","year":"1996","journal-title":"IEEE"},{"key":"atypb12","first-page":"161","author":"Bartal Y.","year":"1998","journal-title":"New York"},{"key":"atypb13","first-page":"663","author":"Bartal Y.","year":"2012","journal-title":"New York"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"H. Bast, S. Funke, D. Matijevic, P. Sanders, and D. Schultes,\n                      In transit to constant time shortest-path queries in road networks\n                      , in Proceedings of the Algorithm Engineering and Experiments, SIAM, Philadelphia, 2007,https:\/\/doi.org\/10.1137\/1.9781611972870.5.","DOI":"10.1137\/1.9781611972870.5"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/074\/07"},{"key":"atypb16","first-page":"1028","author":"Bateni M.","year":"2011","journal-title":"SIAM"},{"key":"atypb17","first-page":"93","author":"Bauer R.","year":"2013","journal-title":"New York"},{"key":"atypb18","unstructured":"G. Borradaile, C. Kenyon-Mathieu, and P. Klein,\n                      A polynomial-time approximation scheme for Steiner tree in planar graphs\n                      , in Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, 2007, pp. 1285-1294."},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/s00407-013-0127-z"},{"key":"atypb20","first-page":"146","author":"Carroll D. E.","year":"2004","journal-title":"New York"},{"key":"atypb21","unstructured":"A. Chakrabarti, A. Jaffe, J. Lee, and J. Vincent,\n                      Local moves and lossy invariants in planar graph embeddings\n                      , in Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008."},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1137\/090749396"},{"key":"atypb23","first-page":"170","author":"Chleb\u00edk M.","year":"2002","journal-title":"New York"},{"key":"atypb24","unstructured":"W. Cook,\n                      In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation\n                      , Princeton University Press, Princeton, NJ, 2012."},{"key":"atypb25","first-page":"201","author":"Engebretsen L.","year":"2001","journal-title":"New York"},{"key":"atypb26","first-page":"448","author":"Fakcharoenphol J.","year":"2003","journal-title":"New York"},{"key":"atypb27","doi-asserted-by":"crossref","unstructured":"A. E. Feldmann,\n                      Fixed parameter approximations for k-center problems in low highway dimension graphs\n                      , in Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming, 2015, pp. 588-600,https:\/\/doi.org\/10.1007\/978-3-662-47666-6_47.","DOI":"10.1007\/978-3-662-47666-6_47"},{"key":"atypb28","unstructured":"M. R. Garey and D. S. Johnson,\n                      Computers and Intractability\n                      , W. H. Freeman, San Francisco, 2002."},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0993"},{"key":"atypb30","first-page":"534","author":"Gupta A.","year":"2003","journal-title":"IEEE"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1137\/060649562"},{"key":"atypb32","first-page":"1462","author":"Kosowski A.","year":"2017","journal-title":"Philadelphia"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703435716"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796309764"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90023-4"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1016\/S0927-0507(05)12001-5"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1057\/jors.2008.172"},{"key":"atypb38","first-page":"281","author":"Talwar K.","year":"2004","journal-title":"New York"},{"key":"atypb39","unstructured":"V. V. Vazirani,\n                      Approximation Algorithms\n                      , Springer, New York, 2001."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M1067196","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:14:57Z","timestamp":1787339697000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1067196"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":38,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/16M1067196"],"URL":"https:\/\/doi.org\/10.1137\/16m1067196","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}