{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:06:16Z","timestamp":1750694776011,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":63,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF (National Science Foundation)","award":["CCF-1527110, CCF-1618280, CCF-1814603, CCF-1910588, CAREER award CCF-1750808"],"award-info":[{"award-number":["CCF-1527110, CCF-1618280, CCF-1814603, CCF-1910588, CAREER award CCF-1750808"]}]},{"name":"Swiss National Foundation","award":["200021-184735"],"award-info":[{"award-number":["200021-184735"]}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-20-1-0080"],"award-info":[{"award-number":["FA9550-20-1-0080"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Sloan Foundation","award":["Sloan Research Fellowship"],"award-info":[{"award-number":["Sloan Research Fellowship"]}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["949272"],"award-info":[{"award-number":["949272"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451053","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"356-369","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Tree embeddings for hop-constrained network design"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3381-0459","authenticated-orcid":false,"given":"Bernhard","family":"Haeupler","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, USA \/ ETH Zurich, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0862-3715","authenticated-orcid":false,"given":"D. Ellis","family":"Hershkowitz","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9322-6329","authenticated-orcid":false,"given":"Goran","family":"Zuzic","sequence":"additional","affiliation":[{"name":"ETH Zurich, Switzerland"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.62"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.108"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1112406"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214015"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792236237"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2011.01.051"},{"key":"e_1_3_2_1_7_1","first-page":"4","article-title":"A general approach to online network optimization problems","volume":"2","author":"Alon Noga","year":"2006","unstructured":"Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Joseph Naor. 2006. A general approach to online network optimization problems. ACM Transactions on Algorithms (TALG), 2, 4, 2006. Pages 640\u2013660.","journal-title":"ACM Transactions on Algorithms (TALG)"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792224474"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2004.05.005"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384321"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1997.646143"},{"key":"e_1_3_2_1_12_1","volume-title":"Foundations of Software Technology and Theoretical Computer Science (FSTTCS)","author":"Babay Amy","year":"2018","unstructured":"Amy Babay, Michael Dinitz, and Zeyu Zhang. 2018. Characterizing demand graphs for (fixed-parameter) shallow-light steiner network. Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2018."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.63"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00130-9"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1996.548477"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276725"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258667"},{"key":"e_1_3_2_1_18_1","volume-title":"Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Pages 1538\u20131557","author":"Bartal Yair","year":"2020","unstructured":"Yair Bartal, Nova Fandina, and Seeun William Umboh. 2020. Online probabilistic metric embedding: a general framework for bypassing inherent bounds. In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Pages 1538\u20131557."},{"key":"e_1_3_2_1_19_1","volume-title":"Annual ACM Symposium on Theory of Computing (STOC). Pages 344\u2013353","author":"Berman Piotr","year":"1997","unstructured":"Piotr Berman and Chris Coulston. 1997. On-line algorithms for Steiner tree problems. In Annual ACM Symposium on Theory of Computing (STOC). Pages 344\u2013353."},{"key":"e_1_3_2_1_20_1","first-page":"1","article-title":"Efficient Construction of Probabilistic Tree Embeddings","volume":"26","author":"Blelloch Guy E.","year":"2017","unstructured":"Guy E. Blelloch, Yan Gu, and Yihan Sun. 2017. Efficient Construction of Probabilistic Tree Embeddings. In International Colloquium on Automata, Languages and Programming (ICALP). 80, Pages 26:1\u201326:14.","journal-title":"International Colloquium on Automata, Languages and Programming (ICALP). 80, Pages"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2013.05.126"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2015.05.009"},{"key":"e_1_3_2_1_23_1","volume-title":"Benders decomposition for the hop-constrained survivable network design problem. INFORMS journal on computing, 25, 1","author":"Botton Quentin","year":"2013","unstructured":"Quentin Botton, Bernard Fortz, Luis Gouveia, and Michael Poss. 2013. Benders decomposition for the hop-constrained survivable network design problem. INFORMS journal on computing, 25, 1, 2013. Pages 13\u201326."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.28"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2017.08.017"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.21667"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s12243-017-0622-3"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Michael Dinitz Guy Kortsarz and Ran Raz. 2012. Min-Rep instances with large supergirth and the hardness of approximating basic spanners. In International Colloquium on Automata Languages and Programming (ICALP).","DOI":"10.1007\/978-3-642-31594-7_25"},{"key":"e_1_3_2_1_29_1","first-page":"2","article-title":"Label cover instances with large girth and the hardness of approximating basic k-spanner","volume":"12","author":"Dinitz Michael","year":"2015","unstructured":"Michael Dinitz, Guy Kortsarz, and Ran Raz. 2015. Label cover instances with large girth and the hardness of approximating basic k-spanner. ACM Transactions on Algorithms (TALG), 12, 2, 2015. Pages 1\u201316.","journal-title":"ACM Transactions on Algorithms (TALG)"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch59"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/050641661"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Michael Elkin and David Peleg. 2000. Strong inapproximability of the basic k-spanner problem. In International Colloquium on Automata Languages and Programming (ICALP). Pages 636\u2013648.","DOI":"10.1007\/3-540-45022-X_54"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.011"},{"key":"e_1_3_2_1_34_1","volume-title":"Dynamic Maintanance of Low-Stretch Probabilistic Tree Embeddings with Applications. arXiv preprint arXiv:2004.10319","author":"Forster Sebastian","year":"2020","unstructured":"Sebastian Forster, Gramoz Goranci, and Monika Henzinger. 2020. Dynamic Maintanance of Low-Stretch Probabilistic Tree Embeddings with Applications. arXiv preprint arXiv:2004.10319, 2020."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1096"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0305-0548(94)00074-I"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(95)00090-9"},{"key":"e_1_3_2_1_38_1","first-page":"3","article-title":"Network flow models for designing diameter-constrained minimum-spanning and Steiner trees. Networks","volume":"41","author":"Gouveia Luis","year":"2003","unstructured":"Luis Gouveia and Thomas L Magnanti. 2003. Network flow models for designing diameter-constrained minimum-spanning and Steiner trees. Networks: An International Journal, 41, 3, 2003. Pages 159\u2013173.","journal-title":"An International Journal"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(00)00143-0"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109665"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2003.1238226"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9013-x"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2008.11.006"},{"key":"e_1_3_2_1_44_1","first-page":"1989","article-title":"A 2k-competitive algorithm for the circle","volume":"5","author":"Karp Richard M","year":"1989","unstructured":"Richard M Karp. 1989. A 2k-competitive algorithm for the circle. Manuscript, August, 5, 1989.","journal-title":"Manuscript"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-012-0157-9"},{"key":"e_1_3_2_1_46_1","volume-title":"Annual International Symposium on Algorithms and Computation (ISAAC). Pages 20\u201329","author":"Reza Khani M","year":"2011","unstructured":"M Reza Khani and Mohammad R Salavatipour. 2011. Improved approximations for buy-at-bulk and shallow-light k-Steiner trees and (k, 2)-subgraph. In Annual International Symposium on Algorithms and Computation (ISAAC). Pages 20\u201329."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1121-2"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(01)00161-2"},{"key":"e_1_3_2_1_49_1","volume-title":"Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Pages 103\u2013110","author":"Kortsarz Guy","year":"1997","unstructured":"Guy Kortsarz and David Peleg. 1997. Approximating shallow-light trees. In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Pages 103\u2013110."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.85"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2015.06.012"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0930"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.65"},{"volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"Nagarajan Viswanath","key":"e_1_3_2_1_54_1","unstructured":"Viswanath Nagarajan and Ramamoorthi Ravi. 2005. Approximation algorithms for requirement cut on graphs. In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques. Springer. Pages 209\u2013220."},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-012-0039-7"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.65"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1997.646142"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2002.1181881"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365693"},{"key":"e_1_3_2_1_60_1","volume-title":"Connectivity-and-hop-constrained design of electricity distribution networks. European journal of operational research, 218, 1","author":"Rossi Andr\u00e9","year":"2012","unstructured":"Andr\u00e9 Rossi, Alexis Aubry, and Mireille Jacomino. 2012. Connectivity-and-hop-constrained design of electricity distribution networks. European journal of operational research, 218, 1, 2012. Pages 48\u201357."},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2014.07.013"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018967121276"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1016\/0305-0548(88)90033-0"}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Virtual Italy","acronym":"STOC '21"},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451053","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451053","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451053","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:44Z","timestamp":1750197704000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451053"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":63,"alternative-id":["10.1145\/3406325.3451053","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451053","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}