{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:06Z","timestamp":1740109326130,"version":"3.37.3"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2022,1,24]],"date-time":"2022-01-24T00:00:00Z","timestamp":1642982400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,24]],"date-time":"2022-01-24T00:00:00Z","timestamp":1642982400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["NSF grants CCF-1566356","CCF- 1717134"],"award-info":[{"award-number":["NSF grants CCF-1566356","CCF- 1717134"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1844890","1910565"],"award-info":[{"award-number":["CCF-1844890","1910565"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Science and Technology Innovation 2030","award":["2018AAA0100903"],"award-info":[{"award-number":["2018AAA0100903"]}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF- 1566356","CCF- 1717134"],"award-info":[{"award-number":["CCF- 1566356","CCF- 1717134"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1844890","CCF- 1566356"],"award-info":[{"award-number":["CCF-1844890","CCF- 1566356"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF- 1717134","CCF-1844890"],"award-info":[{"award-number":["CCF- 1717134","CCF-1844890"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["61932002"],"award-info":[{"award-number":["61932002"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Program for Innovative Research Team of Shanghai University of Finance and Economics"},{"name":"Fundamental Research Funds for the Central Universities and by the 1000-talent award by the Chinese Government"},{"name":"Alexander von Humboldt Foundation with funds from the German Federal Ministry of Education and Research (BMBF)."}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,5]]},"DOI":"10.1007\/s00453-022-00924-0","type":"journal-article","created":{"date-parts":[[2022,1,24]],"date-time":"2022-01-24T13:11:09Z","timestamp":1643029869000},"page":"1252-1278","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On Approximating Degree-Bounded Network Design Problems"],"prefix":"10.1007","volume":"84","author":[{"given":"Xiangyu","family":"Guo","sequence":"first","affiliation":[]},{"given":"Guy","family":"Kortsarz","sequence":"additional","affiliation":[]},{"given":"Bundit","family":"Laekhanukit","sequence":"additional","affiliation":[]},{"given":"Shi","family":"Li","sequence":"additional","affiliation":[]},{"given":"Daniel","family":"Vaz","sequence":"additional","affiliation":[]},{"given":"Jiayi","family":"Xian","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,1,24]]},"reference":[{"key":"924_CR1","unstructured":"Bartal, Yair: Probabilistic approximations of metric spaces and its algorithmic applications. In: 37th Annual Symposium on Foundations of Computer Science, FOCS \u201996, Burlington, Vermont, USA, 14-16 October, 1996, pp. 184\u2013193, (1996)"},{"issue":"1","key":"924_CR2","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1006\/jagm.1999.1042","volume":"33","author":"Moses Charikar","year":"1999","unstructured":"Charikar, Moses, Chekuri, Chandra, Cheung, To-Yat., Dai, Zuo, Goel, Ashish, Guha, Sudipto, Li, Ming: Approximation algorithms for directed steiner problems. J. Algorithms 33(1), 73\u201391 (1999)","journal-title":"J. Algorithms"},{"key":"924_CR3","unstructured":"Dehghani, Sina, Ehsani, Soheil, Hajiaghayi, Mohammad\u00a0Taghi, Liaghat, Vahid, R\u00e4cke, Harald, Seddighin, Saeed: Online weighted degree-bounded steiner networks via novel online mixed packing\/covering. In: 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, pp. 42:1\u201342:14, (2016)"},{"key":"924_CR4","doi-asserted-by":"crossref","unstructured":"Dehghani, Sina, Ehsani, Soheil, Hajiaghayi, MohammadTaghi, Liaghat, Vahid: Online degree-bounded steiner network design. In: Proceedings of the Twenty-seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201916, pp. 164\u2013175, Philadelphia, PA, USA, Society for Industrial and Applied Mathematics. (2016)","DOI":"10.1137\/1.9781611974331.ch13"},{"key":"924_CR5","unstructured":"Dehghani, Sina, Ehsani, Soheil, Hajiaghayi, MohammadTaghi, Liaghat, Vahid, Seddighin, Saeed: Greedy algorithms for online survivable network design. In: 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, pp. 152:1\u2013152:14 (2018)"},{"issue":"3","key":"924_CR6","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1016\/j.jcss.2004.04.011","volume":"69","author":"Jittat Fakcharoenphol","year":"2004","unstructured":"Fakcharoenphol, Jittat, Rao, Satish, Talwar, Kunal: A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci. 69(3), 485\u2013497 (2004)","journal-title":"J. Comput. Syst. Sci."},{"key":"924_CR7","doi-asserted-by":"crossref","unstructured":"Friggstad, Zachary, K\u00f6nemann, Jochen, Kun-Ko, Young, Louis, Anand, Shadravan, Mohammad, Tulsiani, Madhur: Linear programming hierarchies suffice for directed steiner tree. In: Integer Programming and Combinatorial Optimization - 17th International Conference, IPCO 2014, Bonn, Germany, June 23-25, 2014. Proceedings, pp. 285\u2013296 (2014)","DOI":"10.1007\/978-3-319-07557-0_24"},{"issue":"3","key":"924_CR8","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1006\/jagm.1994.1042","volume":"17","author":"Martin F\u00fcrer","year":"1994","unstructured":"F\u00fcrer, Martin, Raghavachari, Balaji: Approximating the minimum-degree steiner tree to within one of optimal. J. Algorithms 17(3), 409\u2013423 (1994)","journal-title":"J. Algorithms"},{"issue":"1","key":"924_CR9","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1006\/jagm.2000.1096","volume":"37","author":"Naveen Garg","year":"2000","unstructured":"Garg, Naveen, Konjevod, Goran, Ravi, R.: A polylogarithmic approximation algorithm for the group steiner tree problem. J. Algorithms 37(1), 66\u201384 (2000)","journal-title":"J. Algorithms"},{"key":"924_CR10","unstructured":"Ghuge, Rohan, Nagarajan, Viswanath: A quasi-polynomial algorithm for submodular tree orienteering in directed graphs. CoRR, arXiv:abs\/1812.01768, (2018)"},{"key":"924_CR11","doi-asserted-by":"crossref","unstructured":"Goemans, Michel\u00a0X.: Minimum bounded degree spanning trees. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS \u201906, pp. 273\u2013282, Washington, DC, USA, IEEE Computer Society (2006)","DOI":"10.1109\/FOCS.2006.48"},{"key":"924_CR12","doi-asserted-by":"crossref","unstructured":"Grandoni, Fabrizio, Laekhanukit, Bundit, Li, Shi: O(log$${}^{\\text{2}}$$k \/ log log k)-approximation algorithm for directed steiner tree: a tight quasi-polynomial-time algorithm. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pp. 253\u2013264 (2019)","DOI":"10.1145\/3313276.3316349"},{"key":"924_CR13","unstructured":"Hajiaghayi, Mohammad\u00a0Taghi: Open problems on bounded-degree network design from 8-th workshop on flexible network design, amsterdam, 2016. Announcement, (2016)"},{"key":"924_CR14","doi-asserted-by":"crossref","unstructured":"Halperin, Eran, Krauthgamer, Robert: Polylogarithmic inapproximability. In: Lawrence\u00a0L. Larmore and Michel\u00a0X. Goemans (eds.) Proceedings of the 35th Annual ACM Symposium on Theory of Computing. San Diego, CA, USA, ACM. pp. 585\u2013594 (2003)","DOI":"10.1145\/780542.780628"},{"issue":"6","key":"924_CR15","doi-asserted-by":"publisher","first-page":"1783","DOI":"10.1137\/S009753970036917X","volume":"31","author":"Jochen K\u00f6nemann","year":"2002","unstructured":"K\u00f6nemann, Jochen, Ravi, R.: A matter of degree: Improved approximation algorithms for degree-bounded minimum spanning trees. SIAM J. Comput. 31(6), 1783\u20131793 (2002)","journal-title":"SIAM J. Comput."},{"key":"924_CR16","doi-asserted-by":"crossref","unstructured":"K\u00f6nemann, Jochen, Ravi, R.: Quasi-polynomial time approximation algorithm for low-degree minimum-cost steiner trees. In: FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science, 23rd Conference, Mumbai, India, December 15-17, 2003, Proceedings, pp. 289\u2013301, (2003)","DOI":"10.1007\/978-3-540-24597-1_25"},{"issue":"3","key":"924_CR17","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1137\/S0097539702418048","volume":"34","author":"Jochen K\u00f6nemann","year":"2005","unstructured":"K\u00f6nemann, Jochen, Ravi, R.: Primal-dual meets local search: Approximating msts with nonuniform degree bounds. SIAM J. Comput. 34(3), 763\u2013773 (2005)","journal-title":"SIAM J. Comput."},{"key":"924_CR18","doi-asserted-by":"crossref","unstructured":"Kortsarz, Guy, Nutov, Zeev: Bounded degree group steiner tree problems. In: IWOCA\u201920, to appear, (2020)","DOI":"10.1007\/978-3-030-48966-3_26"},{"issue":"3","key":"924_CR19","doi-asserted-by":"publisher","first-page":"1062","DOI":"10.1137\/070700620","volume":"39","author":"Lap Chi Lau","year":"2009","unstructured":"Lau, Lap Chi, Naor, Joseph, Salavatipour, Mohammad R., Singh, Mohit: Survivable network design with degree or order constraints. SIAM J. Comput. 39(3), 1062\u20131087 (2009)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"924_CR20","doi-asserted-by":"publisher","first-page":"2217","DOI":"10.1137\/110854461","volume":"42","author":"Lap Chi Lau","year":"2013","unstructured":"Lau, Lap Chi, Singh, Mohit: Additive approximation for bounded degree survivable network design. SIAM J. Comput. 42(6), 2217\u20132242 (2013)","journal-title":"SIAM J. Comput."},{"key":"924_CR21","doi-asserted-by":"crossref","unstructured":"Ravi, R., Marathe, Madhav\u00a0V., Ravi, S.\u00a0S., Rosenkrantz, Daniel\u00a0J., Hunt III, Harry B.: Many birds with one stone: multi-objective approximation algorithms. In: Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 16-18, 1993, San Diego, CA, USA, pp. 438\u2013447, (1993)","DOI":"10.1145\/167088.167209"},{"key":"924_CR22","unstructured":"Rothvo\u00df, Thomas: Directed steiner tree and the lasserre hierarchy. CoRR, arXiv:abs\/1111.5473, (2011)"},{"issue":"1","key":"924_CR23","doi-asserted-by":"publisher","first-page":"1.1","DOI":"10.1145\/2629366","volume":"62","author":"Mohit Singh","year":"2015","unstructured":"Singh, Mohit, Lau, Lap Chi: Approximating minimum bounded degree spanning trees to within one of optimal. J. ACM 62(1), 1.1-1.19 (2015)","journal-title":"J. ACM"},{"issue":"1","key":"924_CR24","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/BF02523690","volume":"18","author":"Alexander Zelikovsky","year":"1997","unstructured":"Zelikovsky, Alexander: A series of approximation algorithms for the acyclic directed steiner tree problem. Algorithmica 18(1), 99\u2013110 (1997)","journal-title":"Algorithmica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00924-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00924-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00924-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,16]],"date-time":"2024-09-16T20:02:34Z","timestamp":1726516954000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00924-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,24]]},"references-count":24,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,5]]}},"alternative-id":["924"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00924-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,1,24]]},"assertion":[{"value":"21 September 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 January 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 January 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}