{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,10]],"date-time":"2025-09-10T22:58:52Z","timestamp":1757545132165,"version":"3.37.3"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2022,8,5]],"date-time":"2022-08-05T00:00:00Z","timestamp":1659657600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,8,5]],"date-time":"2022-08-05T00:00:00Z","timestamp":1659657600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11971146"],"award-info":[{"award-number":["11971146"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comp. Appl. Math."],"published-print":{"date-parts":[[2022,9]]},"DOI":"10.1007\/s40314-022-01984-2","type":"journal-article","created":{"date-parts":[[2022,8,5]],"date-time":"2022-08-05T10:08:17Z","timestamp":1659694097000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["An approximation algorithm for the group prize-collecting Steiner tree problem with submodular penalties"],"prefix":"10.1007","volume":"41","author":[{"given":"Jiaxuan","family":"Zhang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Suogang","family":"Gao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bo","family":"Hou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wen","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,8,5]]},"reference":[{"key":"1984_CR1","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1137\/S0097539792236237","volume":"24","author":"A Agrawal","year":"1995","unstructured":"Agrawal A, Klein P, Ravi R (1995) When trees collide: an approximation algorithm for the generalized Steiner problem on networks. SIAM J Comput 24:440\u2013456","journal-title":"SIAM J Comput"},{"key":"1984_CR2","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1007\/BF01581256","volume":"59","author":"D Bienstock","year":"1993","unstructured":"Bienstock D, Goemans MX, Simchi-Levi D, Williamson D (1993) A note on the prize collecting traveling salesman problem. Math Program 59:413\u2013420","journal-title":"Math Program"},{"key":"1984_CR3","unstructured":"Chekury C, Even G, Kortsarz G (2002) An approximation algorithm for the group Steiner problem. In: Proceedings of the symposium on discrete algorithms SODA, San Francisco, California, pp 49\u201358"},{"issue":"1","key":"1984_CR4","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1109\/TKDE.2012.228","volume":"26","author":"J Coffman","year":"2014","unstructured":"Coffman J, Weaver AC (2014) An empirical performance evaluation of relational keyword search techniques. IEEE Trans Knowl Data Eng 26(1):30\u201342","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"1984_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-1701-9","volume-title":"Design and analysis of approximation algorithm","author":"DZ Du","year":"2012","unstructured":"Du DZ, Ko KI, Hu XD (2012) Design and analysis of approximation algorithm. Springer, New York"},{"key":"1984_CR6","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1023\/A:1009881326671","volume":"4","author":"M Dror","year":"2000","unstructured":"Dror M, Haurari M (2000) Generalized steiner problem and other variants. J Comb Optim 4:415\u2013436","journal-title":"J Comb Optim"},{"key":"1984_CR7","first-page":"11","volume-title":"Combinatorial optimization-Uureka, You Shrink! Lecture notes in computer science","author":"J Edmonds","year":"2003","unstructured":"Edmonds J (2003) Submodular functions, matroids, and certain polyhedra. In: J\u00fcnger M, Reinelt G, Rinaldi G (eds) Combinatorial optimization-Uureka, You Shrink! Lecture notes in computer science. Springer, Berlin, pp 11\u201326"},{"issue":"6","key":"1984_CR8","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1016\/0041-5553(67)90123-1","volume":"7","author":"II Er\u00ebmin","year":"1967","unstructured":"Er\u00ebmin II, Kostina MA (1967) The penalty method in linear programming and its realization on a computer. USSR Comput Math Math Phys 7(6):188\u2013200","journal-title":"USSR Comput Math Math Phys"},{"key":"1984_CR9","volume-title":"Submodular functions and optimization","author":"S Fujieshige","year":"2005","unstructured":"Fujieshige S (2005) Submodular functions and optimization, 2nd edn. Elsevier Science, New York","edition":"2"},{"key":"1984_CR10","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1006\/jagm.2000.1096","volume":"37","author":"N Garg","year":"2000","unstructured":"Garg N, Konjevod G, Ravi R (2000) A polylogarithmic approximation algorithm for the group Steiner tree problem. J Algorithms 37:66\u201384","journal-title":"J Algorithms"},{"key":"1984_CR11","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/S0377-2217(99)00073-9","volume":"122","author":"G Ghiani","year":"2000","unstructured":"Ghiani G, Improta G (2000) An efficient transformation of the generalized vehicle routing problem. Eur J Oper Res 122:11\u201317","journal-title":"Eur J Oper Res"},{"key":"1984_CR12","doi-asserted-by":"publisher","first-page":"3238","DOI":"10.1016\/j.dam.2008.05.013","volume":"156","author":"H Glicksman","year":"2008","unstructured":"Glicksman H, Penn M (2008) Approximation algorithms for group prize-collecting and location-routing problems. Discret Appl Math 156:3238\u20133247","journal-title":"Discret Appl Math"},{"key":"1984_CR13","doi-asserted-by":"crossref","unstructured":"Goel G, Karande C, Tripathi P, Wang L (2009) Approximability of combinatorial problems with multi-agent submodular cost functions. In: 50th annual IEEE symposium on foundations of computer science, Atlanta, GA, pp 755\u2013764","DOI":"10.1109\/FOCS.2009.81"},{"key":"1984_CR14","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1137\/S0097539793242618","volume":"24","author":"MX Goemans","year":"1995","unstructured":"Goemans MX, Williamson DP (1995) A general approximation technique for constrained forest problems. SIAM J Comput 24:296\u2013317","journal-title":"SIAM J Comput"},{"key":"1984_CR15","doi-asserted-by":"crossref","unstructured":"Hajiaghayi MT, Jain K (2006) 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. Society for Industry and Applied Mathematics, New York, pp 631\u2013640","DOI":"10.1145\/1109557.1109626"},{"key":"1984_CR16","doi-asserted-by":"crossref","unstructured":"Hajiaghayi MT, Khandekar R, Kortsarz G, Nutov Z (2010) Prize-collecting Steiner network problems. In: Eisenbrand F, Shepherd FB (eds) Integer programming and combinatorial optimization, IPCO 2010. Lecture notes in computer science, vol 6080, pp 79\u201384","DOI":"10.1007\/978-3-642-13036-6_6"},{"issue":"5","key":"1984_CR17","doi-asserted-by":"publisher","first-page":"1494","DOI":"10.1137\/S0097539704445718","volume":"36","author":"E Halperin","year":"2007","unstructured":"Halperin E, Kortsarz G, Krauthgamer R, Srinivasan A, Wang N (2007) Integrality ratio for group Steiner trees and directed Steiner trees. SIAM J Comput 36(5):1494\u20131511","journal-title":"SIAM J Comput"},{"issue":"2","key":"1984_CR18","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/s40305-017-0164-4","volume":"5","author":"L Han","year":"2017","unstructured":"Han L, Xu DC, Du DL, Wu CC (2017) A primal-dual algorithm for the generalized prize-collecting Steiner forest problem. J Oper Res Soc China 5(2):219\u2013231","journal-title":"J Oper Res Soc China"},{"key":"1984_CR19","unstructured":"Hayrapetyan A, Swamy C, Tardos \u00c9 (2005) Network design for information networks. In: Proceedings of the 16th annual ACM-SIAM symposium on discrete algorithms, pp 933\u2013942"},{"key":"1984_CR20","unstructured":"Maniu S, Senellart P, Jog S (2019) An experimental study of the treewidth of real-world graph data. In: 22nd international conference on database theory, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, pp 1\u201318"},{"key":"1984_CR21","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1002\/net.3230260407","volume":"26","author":"YS Myulg","year":"1995","unstructured":"Myulg YS, Lee CH, Tcha DW (1995) On the generalized minimum spanning tree problem. Networks 26:231\u2013241","journal-title":"Networks"},{"key":"1984_CR22","doi-asserted-by":"crossref","unstructured":"Reich G, Widmayer P (1989) Beyond Steiner\u2019s problem, a VLSI oriented generalization. In: Lecture notes in computer science, vol 411, pp 196\u2013211","DOI":"10.1007\/3-540-52292-1_14"},{"key":"1984_CR23","unstructured":"Sharma Y, Swamy C, Williamson DP (2007) Approximation algorithms for prize collecting forest problems with submodular penalty functions. In: Proceedings of the 18th annual ACM-SIAM symposium on discrete algorithms. Society for Industry and Applied Mathematics, pp 1275\u20131284"}],"container-title":["Computational and Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s40314-022-01984-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s40314-022-01984-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s40314-022-01984-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,9]],"date-time":"2022-09-09T22:31:16Z","timestamp":1662762676000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s40314-022-01984-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,5]]},"references-count":23,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,9]]}},"alternative-id":["1984"],"URL":"https:\/\/doi.org\/10.1007\/s40314-022-01984-2","relation":{},"ISSN":["2238-3603","1807-0302"],"issn-type":[{"type":"print","value":"2238-3603"},{"type":"electronic","value":"1807-0302"}],"subject":[],"published":{"date-parts":[[2022,8,5]]},"assertion":[{"value":"10 November 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 July 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 July 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 August 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"274"}}