{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,11]],"date-time":"2025-12-11T07:43:01Z","timestamp":1765438981973,"version":"3.40.3"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031630200"},{"type":"electronic","value":"9783031630217"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-3-031-63021-7_21","type":"book-chapter","created":{"date-parts":[[2024,6,21]],"date-time":"2024-06-21T13:02:29Z","timestamp":1718974949000},"page":"273-286","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Approximation Algorithms for\u00a0Node-Weighted Directed Steiner Problems"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0377-7037","authenticated-orcid":false,"given":"Gianlorenzo","family":"D\u2019Angelo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9642-7652","authenticated-orcid":false,"given":"Esmaeil","family":"Delfaraz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,6,22]]},"reference":[{"issue":"2","key":"21_CR1","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1137\/090771429","volume":"40","author":"A Archer","year":"2011","unstructured":"Archer, A., Bateni, M.H., Hajiaghayi, M.T., Karloff, H.J.: Improved approximation algorithms for prize-collecting steiner tree and TSP. SIAM J. Comput. 40(2), 309\u2013332 (2011)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"21_CR2","doi-asserted-by":"publisher","first-page":"1275","DOI":"10.1137\/15M102695X","volume":"47","author":"MH Bateni","year":"2018","unstructured":"Bateni, M.H., Hajiaghayi, M.T., Liaghat, V.: Improved approximation algorithms for (budgeted) node-weighted steiner problems. SIAM J. Comput. 47(4), 1275\u20131293 (2018)","journal-title":"SIAM J. Comput."},{"key":"21_CR3","doi-asserted-by":"crossref","unstructured":"Chan, T.M.: More algorithms for all-pairs shortest paths in weighted graphs. In: Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, STOC 2007, pp. 590\u2013598. Association for Computing Machinery (2007)","DOI":"10.1145\/1250790.1250877"},{"issue":"1","key":"21_CR4","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1006\/jagm.1999.1042","volume":"33","author":"M Charikar","year":"1999","unstructured":"Charikar, M., et al.: Approximation algorithms for directed steiner problems. J. Algorithms 33(1), 73\u201391 (1999)","journal-title":"J. Algorithms"},{"key":"21_CR5","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/0-387-23830-1_4","volume-title":"Handbook of Combinatorial Optimization","author":"X Cheng","year":"2004","unstructured":"Cheng, X., Li, Y., Du, D.-Z., Ngo, H.Q.: Steiner trees in industry. In: Du, D.Z., Pardalos, P.M. (eds.) Handbook of Combinatorial Optimization, pp. 193\u2013216. Springer, Boston (2004). https:\/\/doi.org\/10.1007\/0-387-23830-1_4"},{"key":"21_CR6","unstructured":"D\u2019Angelo, G., Delfaraz, E.: Approximation algorithms for node-weighted steiner problems: digraphs with additive prizes and graphs with submodular prizes. arXiv preprint arXiv:2211.03653 (2022)"},{"key":"21_CR7","unstructured":"D\u2019Angelo, G., Delfaraz, E., Gilbert, H.: Budgeted out-tree maximization with submodular prizes. In: Bae, S.W., Park, H. (eds.) 33rd International Symposium on Algorithms and Computation, ISAAC 2022, 19\u201321 December 2022, Seoul, Korea. LIPIcs, vol. 248, pp. 9:1\u20139:19. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022)"},{"key":"21_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/978-3-030-80879-2_7","volume-title":"Approximation and Online Algorithms","author":"M Dinitz","year":"2021","unstructured":"Dinitz, M., Nazari, Y., Zhang, Z.: Lasserre integrality gaps for graph spanners and related problems. In: Kaklamanis, C., Levin, A. (eds.) WAOA 2020. LNCS, vol. 12806, pp. 97\u2013112. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-80879-2_7"},{"key":"21_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/978-3-319-07557-0_24","volume-title":"Integer Programming and Combinatorial Optimization","author":"Z Friggstad","year":"2014","unstructured":"Friggstad, Z., K\u00f6nemann, J., Kun-Ko, Y., Louis, A., Shadravan, M., Tulsiani, M.: Linear programming hierarchies suffice for directed steiner tree. In: Lee, J., Vygen, J. (eds.) IPCO 2014. LNCS, vol. 8494, pp. 285\u2013296. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-07557-0_24"},{"issue":"10","key":"21_CR10","doi-asserted-by":"publisher","first-page":"2257","DOI":"10.1109\/TMC.2018.2874650","volume":"18","author":"X Gao","year":"2019","unstructured":"Gao, X., Junwei, L., Wang, H., Fan, W., Chen, G.: Algorithm design and analysis for wireless relay network deployment problem. IEEE Trans. Mob. Comput. 18(10), 2257\u20132269 (2019)","journal-title":"IEEE Trans. Mob. Comput."},{"key":"21_CR11","doi-asserted-by":"crossref","unstructured":"Garg, N.: Saving an epsilon: a 2-approximation for the k-MST problem in graphs. In: Gabow, H.N., Fagin, R. (eds.) Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pp. 396\u2013402. ACM (2005)","DOI":"10.1145\/1060590.1060650"},{"key":"21_CR12","doi-asserted-by":"crossref","unstructured":"Ghuge, R., Nagarajan, V.: Quasi-polynomial algorithms for submodular tree orienteering and other directed network design problems. In: Chawla, S. (ed.) Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 1039\u20131048. SIAM (2020)","DOI":"10.1137\/1.9781611975994.63"},{"issue":"2","key":"21_CR13","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."},{"key":"21_CR14","doi-asserted-by":"crossref","unstructured":"Grandoni, F., Laekhanukit, B., Li, S.: O(log$${}^{\\text{2}}$$k \/ log log k)-approximation algorithm for directed steiner tree: a tight quasi-polynomial-time algorithm. In: Charikar, M., Cohen, E. (eds.) Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, 23\u201326 June 2019, pp. 253\u2013264. ACM (2019)","DOI":"10.1145\/3313276.3316349"},{"key":"21_CR15","doi-asserted-by":"crossref","unstructured":"Guha, S., Moss, A., Naor, J., Schieber, B.: Efficient recovery from power outage (extended abstract). In: Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, pp. 574\u2013582. ACM (1999)","DOI":"10.1145\/301250.301406"},{"key":"21_CR16","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2020.105940","volume":"158","author":"DS Hochbaum","year":"2020","unstructured":"Hochbaum, D.S., Rao, X.: Approximation algorithms for connected maximum coverage problem for the discovery of mutated driver pathways in cancer. Inf. Process. Lett. 158, 105940 (2020)","journal-title":"Inf. Process. Lett."},{"key":"21_CR17","unstructured":"Johnson, D. S., Minkoff, M., Phillips, S.: The prize collecting steiner tree problem: theory and practice. In: Shmoys, D.B. (ed.) Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 760\u2013769. ACM\/SIAM (2000)"},{"key":"21_CR18","doi-asserted-by":"crossref","unstructured":"K\u00f6nemann, J., Sadeghabad, S.S., Sanit\u00e0, L.: An LMP o(log n)-approximation algorithm for node weighted prize collecting steiner tree. In: 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26\u201329 October 2013, Berkeley, CA, USA, pp. 568\u2013577. IEEE Computer Society (2013)","DOI":"10.1109\/FOCS.2013.67"},{"issue":"35","key":"21_CR19","doi-asserted-by":"publisher","first-page":"4482","DOI":"10.1016\/j.tcs.2011.04.013","volume":"412","author":"G Kortsarz","year":"2011","unstructured":"Kortsarz, G., Nutov, Z.: Approximating some network design problems with node costs. Theor. Comput. Sci. 412(35), 4482\u20134492 (2011)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"21_CR20","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1109\/TNET.2014.2301816","volume":"23","author":"T-W Kuo","year":"2015","unstructured":"Kuo, T.-W., Lin, K.C.-J., Tsai, M.-J.: Maximizing submodular set function with connectivity constraint: theory and application to networks. IEEE\/ACM Trans. Netw. 23(2), 533\u2013546 (2015)","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"21_CR21","doi-asserted-by":"crossref","unstructured":"Li, S., Laekhanukit, B.: Polynomial integrality gap of flow LP for directed steiner tree. In: Naor, J.S., Buchbinder, N. (eds.) Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, pp. 3230\u20133236. SIAM (2022)","DOI":"10.1137\/1.9781611977073.126"},{"issue":"2","key":"21_CR22","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1137\/S0097539702420474","volume":"37","author":"A Moss","year":"2007","unstructured":"Moss, A., Rabani, Y.: Approximation algorithms for constrained node weighted steiner tree problems. SIAM J. Comput. 37(2), 460\u2013481 (2007)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"21_CR23","doi-asserted-by":"publisher","first-page":"576","DOI":"10.1287\/moor.2019.1002","volume":"45","author":"A Paul","year":"2020","unstructured":"Paul, A., Freund, D., Ferber, A.M., Shmoys, D.B., Williamson, D.P.: Budgeted prize-collecting traveling salesman and minimum spanning tree problems. Math. Oper. Res. 45(2), 576\u2013590 (2020)","journal-title":"Math. Oper. Res."},{"key":"21_CR24","unstructured":"Rothvo\u00df, T.: Directed steiner tree and the lasserre hierarchy. CoRR, abs\/1111.5473 (2011)"},{"issue":"3","key":"21_CR25","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1089\/cmb.2010.0265","volume":"18","author":"F Vandin","year":"2011","unstructured":"Vandin, F., Upfal, E., Raphael, B.J.: Algorithms for detecting significantly mutated pathways in cancer. J. Comput. Biol. 18(3), 507\u2013522 (2011)","journal-title":"J. Comput. Biol."},{"issue":"1","key":"21_CR26","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/BF02523690","volume":"18","author":"A Zelikovsky","year":"1997","unstructured":"Zelikovsky, A.: A series of approximation algorithms for the acyclic directed steiner tree problem. Algorithmica 18(1), 99\u2013110 (1997)","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-63021-7_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,22]],"date-time":"2024-11-22T10:57:55Z","timestamp":1732273075000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-63021-7_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031630200","9783031630217"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-63021-7_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"22 June 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IWOCA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Combinatorial Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Ischia","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 July 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 July 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"35","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"iwoca2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/iwoca2024.di.unisa.it","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}