{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:24:14Z","timestamp":1742912654911,"version":"3.40.3"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030046927"},{"type":"electronic","value":"9783030046934"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-030-04693-4_6","type":"book-chapter","created":{"date-parts":[[2018,11,28]],"date-time":"2018-11-28T05:03:12Z","timestamp":1543381392000},"page":"87-101","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Approximating Node-Weighted k-MST on Planar Graphs"],"prefix":"10.1007","author":[{"given":"Jaros\u0142aw","family":"Byrka","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mateusz","family":"Lewandowski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2601-6452","authenticated-orcid":false,"given":"Joachim","family":"Spoerhase","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,11,29]]},"reference":[{"issue":"3","key":"6_CR1","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1007\/s10107-005-0693-1","volume":"107","author":"S Arora","year":"2006","unstructured":"Arora, S., Karakostas, G.: A $$(2 + \\varepsilon )$$-approximation algorithm for the $$k$$-MST problem. Math. Program. 107(3), 491\u2013504 (2006). https:\/\/doi.org\/10.1007\/s10107-005-0693-1","journal-title":"Math. Program."},{"key":"6_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/978-3-642-39206-1_8","volume-title":"Automata, Languages, and Programming","author":"MH Bateni","year":"2013","unstructured":"Bateni, M.H., Hajiaghayi, M.T., Liaghat, V.: Improved approximation algorithms for (budgeted) node-weighted steiner problems. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013. LNCS, vol. 7965, pp. 81\u201392. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-39206-1_8"},{"key":"6_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1007\/978-3-642-32512-0_5","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"P Berman","year":"2012","unstructured":"Berman, P., Yaroslavtsev, G.: Primal-dual approximation algorithms for node-weighted network design in planar graphs. In: Gupta, A., Jansen, K., Rolim, J., Servedio, R. (eds.) APPROX\/RANDOM -2012. LNCS, vol. 7408, pp. 50\u201360. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-32512-0_5"},{"key":"6_CR4","doi-asserted-by":"publisher","unstructured":"Byrka, J., Lewandowski, M., Moldenhauer, C.: Approximation algorithms for node-weighted prize-collecting Steiner tree problems on planar graphs. In: Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016), pp. 2:1\u20132:14 (2016). https:\/\/doi.org\/10.4230\/LIPIcs.SWAT.2016.2","DOI":"10.4230\/LIPIcs.SWAT.2016.2"},{"key":"6_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1007\/978-3-642-31594-7_18","volume-title":"Automata, Languages, and Programming","author":"C Chekuri","year":"2012","unstructured":"Chekuri, C., Ene, A., Vakilian, A.: Node-weighted network design in planar and minor-closed families of graphs. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012. LNCS, vol. 7391, pp. 206\u2013217. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-31594-7_18"},{"key":"6_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1007\/978-3-642-32512-0_9","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"C Chekuri","year":"2012","unstructured":"Chekuri, C., Ene, A., Vakilian, A.: Prize-collecting survivable network design in node-weighted graphs. In: Gupta, A., Jansen, K., Rolim, J., Servedio, R. (eds.) APPROX\/RANDOM -2012. LNCS, vol. 7408, pp. 98\u2013109. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-32512-0_9"},{"issue":"2","key":"6_CR7","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/s10107-003-0479-2","volume":"100","author":"FA Chudak","year":"2004","unstructured":"Chudak, F.A., Roughgarden, T., Williamson, D.P.: Approximate $$k$$-MSTs and $$k$$-Steiner trees via the primal-dual method and lagrangean relaxation. Math. Program. 100(2), 411\u2013421 (2004). https:\/\/doi.org\/10.1007\/s10107-003-0479-2","journal-title":"Math. Program."},{"issue":"3","key":"6_CR8","doi-asserted-by":"publisher","first-page":"13:1","DOI":"10.1145\/2601070","volume":"10","author":"ED Demaine","year":"2014","unstructured":"Demaine, E.D., Hajiaghayi, M.T., Klein, P.N.: Node-weighted Steiner tree and group Steiner tree in planar graphs. ACM Trans. Algorithms 10(3), 13:1\u201313:20 (2014). https:\/\/doi.org\/10.1145\/2601070","journal-title":"ACM Trans. Algorithms"},{"key":"6_CR9","doi-asserted-by":"publisher","unstructured":"Garg, N.: A 3-approximation for the minimum tree spanning k vertices. In: Proceedings of the 37th Annual Symposium on Foundations of Computer Science (FOCS 1996), pp. 302\u2013309 (1996). https:\/\/doi.org\/10.1109\/SFCS.1996.548489","DOI":"10.1109\/SFCS.1996.548489"},{"key":"6_CR10","doi-asserted-by":"publisher","unstructured":"Garg, N.: Saving an epsilon: a 2-approximation for the k-MST problem in graphs. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC 2005), pp. 396\u2013402 (2005). https:\/\/doi.org\/10.1145\/1060590.1060650","DOI":"10.1145\/1060590.1060650"},{"issue":"2","key":"6_CR11","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). https:\/\/doi.org\/10.1137\/S0097539793242618","journal-title":"SIAM J. Comput."},{"issue":"2","key":"6_CR12","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1145\/375827.375845","volume":"48","author":"K Jain","year":"2001","unstructured":"Jain, K., Vazirani, V.V.: Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation. J. ACM 48(2), 274\u2013296 (2001). https:\/\/doi.org\/10.1145\/375827.375845","journal-title":"J. ACM"},{"issue":"4","key":"6_CR13","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1007\/s00453-009-9317-0","volume":"59","author":"J K\u00f6nemann","year":"2011","unstructured":"K\u00f6nemann, J., Parekh, O., Segev, D.: A unified approach to approximating partial covering problems. Algorithmica 59(4), 489\u2013509 (2011). https:\/\/doi.org\/10.1007\/s00453-009-9317-0","journal-title":"Algorithmica"},{"key":"6_CR14","doi-asserted-by":"publisher","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: Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013), pp. 568\u2013577 (2013). https:\/\/doi.org\/10.1109\/FOCS.2013.67","DOI":"10.1109\/FOCS.2013.67"},{"key":"6_CR15","doi-asserted-by":"publisher","unstructured":"Mestre, J.: Lagrangian relaxation and partial cover. In: Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2008), pp. 539\u2013550 (2008). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2008.1315","DOI":"10.4230\/LIPIcs.STACS.2008.1315"},{"key":"6_CR16","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/j.ic.2012.10.017","volume":"222","author":"C Moldenhauer","year":"2013","unstructured":"Moldenhauer, C.: Primal-dual approximation algorithms for node-weighted Steiner forest on planar graphs. Inf. Comput. 222, 293\u2013306 (2013). https:\/\/doi.org\/10.1016\/j.ic.2012.10.017","journal-title":"Inf. Comput."},{"issue":"2","key":"6_CR17","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). https:\/\/doi.org\/10.1137\/S0097539702420474","journal-title":"SIAM J. Comput."},{"key":"6_CR18","unstructured":"Ravi, R., Sundaram, R., Marathe, M.V., Rosenkrantz, D.J., Ravi, S.S.: Spanning trees short or small. In: Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 23\u201325 January 1994, Arlington, Virginia, pp. 546\u2013555 (1994)"},{"key":"6_CR19","unstructured":"Sadeghabad, S.S.: Node-weighted prize-collecting Steiner tree and applications. Master\u2019s thesis (2013)"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-04693-4_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T13:22:56Z","timestamp":1710249776000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-04693-4_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783030046927","9783030046934"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-04693-4_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"29 November 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WAOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Approximation and Online Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Helsinki","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Finland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 August 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 August 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"waoa2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/algo2018.hiit.fi\/waoa\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}