{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,30]],"date-time":"2026-01-30T04:23:20Z","timestamp":1769747000672,"version":"3.49.0"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,3,24]],"date-time":"2021-03-24T00:00:00Z","timestamp":1616544000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,3,24]],"date-time":"2021-03-24T00:00:00Z","timestamp":1616544000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2021,6]]},"DOI":"10.1007\/s11590-021-01727-y","type":"journal-article","created":{"date-parts":[[2021,3,24]],"date-time":"2021-03-24T14:03:47Z","timestamp":1616594627000},"page":"1475-1483","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["An approximation algorithm for the k-generalized Steiner forest problem"],"prefix":"10.1007","volume":"15","author":[{"given":"Jiawen","family":"Gao","sequence":"first","affiliation":[]},{"given":"Suogang","family":"Gao","sequence":"additional","affiliation":[]},{"given":"Wen","family":"Liu","sequence":"additional","affiliation":[]},{"given":"Weili","family":"Wu","sequence":"additional","affiliation":[]},{"given":"Ding-Zhu","family":"Du","sequence":"additional","affiliation":[]},{"given":"Bo","family":"Hou","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,3,24]]},"reference":[{"key":"1727_CR1","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1137\/S0097539792236237","volume":"24","author":"A Agrawal","year":"1995","unstructured":"Agrawal, A., Klein, P., Rawi, R.: When trees collide: an approximation algorithm for the generalized Steiner problem on networks. SIAM J. Comput. 24, 440\u2013456 (1995)","journal-title":"SIAM J. Comput."},{"key":"1727_CR2","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/j.tcs.2018.11.029","volume":"788","author":"E Angel","year":"2019","unstructured":"Angel, E., Thang, N.K., Singh, S.: Approximating $$k$$-forest with resource augmentation: a primal-dual approach. Theor. Comput. Sci. 788, 12\u201320 (2019)","journal-title":"Theor. Comput. Sci."},{"key":"1727_CR3","unstructured":"Arora, S., Karakostas, G.: A $$2+\\varepsilon $$ approximation algorithm for the $$k$$-MST problem. In: Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 754\u2013759 (2000)"},{"key":"1727_CR4","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/S0020-0190(98)00010-6","volume":"65","author":"S Arya","year":"1998","unstructured":"Arya, S., Ramesh, H.: A $$2.5$$-factor approximation algorithm for the $$k$$-MST problem. Inf. Process. Lett. 65, 117\u2013118 (1998)","journal-title":"Inf. Process. Lett."},{"key":"1727_CR5","doi-asserted-by":"publisher","first-page":"6:1","DOI":"10.1145\/2432622.2432628","volume":"60","author":"J Byrka","year":"2013","unstructured":"Byrka, J., Grandoni, F., Rothvoss, T., Sanit\u00e0, L.: Steiner tree approximation via iterative randomized rounding. J. ACM 60, 6:1-6:33 (2013)","journal-title":"J. ACM"},{"key":"1727_CR6","doi-asserted-by":"crossref","unstructured":"Chudak, F.A., Roughgarden, T., Williamson, D.P.: Approximate $$k$$-MSTs and $$k$$-Steiner trees via the primal-dual method and Lagrangean relaxation. In: Proceedings of the 8th Conference on Integer Programming and Combinatorial Optimization, pp. 60\u201370 (2001)","DOI":"10.1007\/3-540-45535-3_5"},{"issue":"3","key":"1727_CR7","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1007\/s004530010050","volume":"29","author":"U Feige","year":"2001","unstructured":"Feige, U., Kortsarz, G., Peleg, D.: The dense $$k$$-subgraph problem. Algorithmica 29(3), 410\u2013421 (2001)","journal-title":"Algorithmica"},{"key":"1727_CR8","unstructured":"Garg, N.: A $$3$$-approximation for the minimum tree spanning $$k$$ vertices. In: Proceedings of the 37th Symposium on Foundations of Computer Science, pp. 302\u2013309 (1996)"},{"key":"1727_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/0116001","volume":"16","author":"EN Gilbert","year":"1968","unstructured":"Gilbert, E.N., Pollak, H.O.: Steiner minimal trees. SIAM J. Appl. Math. 16, 1\u201329 (1968)","journal-title":"SIAM J. Appl. Math."},{"issue":"2","key":"1727_CR10","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1137\/S0097539793242618","volume":"24","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: A general approximation technique for constrained forest problems. SIAM J. Comput. 24(2), 296\u2013317 (1995)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"1727_CR11","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1145\/1721837.1721857","volume":"6","author":"A Gupta","year":"2010","unstructured":"Gupta, A., Hajiaghayi, M., Nagarajan, V., et al.: Dial a ride from $$k$$-forest. ACM Trans. Algorithms 6(2), 41 (2010)","journal-title":"ACM Trans. Algorithms"},{"key":"1727_CR12","doi-asserted-by":"crossref","unstructured":"Hajiaghayi, M.T., Jain, K.: The prize-collecting generalized Steiner tree problem via a new approach of primal-dual schema. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 631\u2013640 (2006)","DOI":"10.1145\/1109557.1109626"},{"key":"1727_CR13","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1023\/A:1009758919736","volume":"1","author":"M Karpinski","year":"1997","unstructured":"Karpinski, M., Zelikovsky, A.: New approximation algorithms for the Steiner tree problems. J. Comb. Optim. 1, 47\u201365 (1997)","journal-title":"J. Comb. Optim."},{"key":"1727_CR14","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1137\/S0895480101393155","volume":"19","author":"G Robins","year":"2005","unstructured":"Robins, G., Zelikovsky, A.: Tighter bounds for graph Steiner tree approximation. SIAM J. Discrete Math. 19, 122\u2013134 (2005)","journal-title":"SIAM J. Discrete Math."},{"key":"1727_CR15","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1006\/jagm.2000.1086","volume":"36","author":"HJ Pr\u00f6mel","year":"2000","unstructured":"Pr\u00f6mel, H.J., Steger, A.: A new approximation algorithm for the Steiner tree problem with performance ratio $$5\/3$$. J. Algorithms 36, 89\u2013101 (2000)","journal-title":"J. Algorithms"},{"issue":"4","key":"1727_CR16","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1007\/s00453-008-9189-8","volume":"56","author":"D Segev","year":"2010","unstructured":"Segev, D., Sege, G.: Approximate $$k$$-Steiner forests via the Lagrangian relaxation technique with internal preprocessing. Algorithmica 56(4), 529\u2013549 (2010)","journal-title":"Algorithmica"},{"key":"1727_CR17","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/BF01187035","volume":"9","author":"A Zelikovsky","year":"1993","unstructured":"Zelikovsky, A.: An $$11\/6$$-approximation algorithm for the network Steiner problem. Algorithmica 9, 463\u2013470 (1993)","journal-title":"Algorithmica"},{"issue":"7\u20138","key":"1727_CR18","doi-asserted-by":"publisher","first-page":"1240","DOI":"10.1016\/j.dam.2012.01.016","volume":"160","author":"P Zhang","year":"2012","unstructured":"Zhang, P., Zhu, D., Luan, J.: An approximation algorithm for the generalized $$k$$-multicut problem. Discrete Appl. Math. 160(7\u20138), 1240\u20131247 (2012)","journal-title":"Discrete Appl. Math."}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-021-01727-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-021-01727-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-021-01727-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,7]],"date-time":"2021-05-07T19:13:18Z","timestamp":1620414798000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-021-01727-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,24]]},"references-count":18,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["1727"],"URL":"https:\/\/doi.org\/10.1007\/s11590-021-01727-y","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"value":"1862-4472","type":"print"},{"value":"1862-4480","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,3,24]]},"assertion":[{"value":"22 January 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 March 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 March 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}