{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:43:42Z","timestamp":1740109422081,"version":"3.37.3"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2020,2,3]],"date-time":"2020-02-03T00:00:00Z","timestamp":1580688000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,2,3]],"date-time":"2020-02-03T00:00:00Z","timestamp":1580688000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004442","name":"Narodowym Centrum Nauki","doi-asserted-by":"publisher","award":["2015\/18\/E\/ST6\/00456"],"award-info":[{"award-number":["2015\/18\/E\/ST6\/00456"]}],"id":[{"id":"10.13039\/501100004442","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2015\/18\/E\/ST6\/00456"],"award-info":[{"award-number":["2015\/18\/E\/ST6\/00456"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2020,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study the problem of finding a minimum weight connected subgraph spanning at least <jats:italic>k<\/jats:italic> vertices on planar, node-weighted graphs. We give a (4 + <jats:italic>\u03b5<\/jats:italic>)-approximation algorithm for this problem. We achieve this by utilizing the recent Lagrangian-multiplier preserving (LMP) primal-dual 3-approximation for the node-weighted prize-collecting Steiner tree problem by Byrka et al. (SWAT\u201916) and adopting an approach by Chudak et al. (Math. Prog. \u201904) regarding Lagrangian relaxation for the edge-weighted variant. In particular, we improve the procedure of picking additional vertices (tree merging procedure) given by Sadeghian (2013) by taking a constant number of recursive steps and utilizing the limited guessing procedure of Arora and Karakostas (Math. Prog. \u201906). More generally, our approach readily gives a (4\/3 \u22c5 <jats:italic>r<\/jats:italic> + <jats:italic>\u03b5<\/jats:italic>)-approximation on any graph class where the algorithm of Byrka et al. for the prize-collecting version gives an <jats:italic>r<\/jats:italic>-approximation. We argue that this can be interpreted as a generalization of an analogous result by K\u00f6nemann et al. (Algorithmica \u201911) for partial cover problems. Together with a lower bound construction by Mestre (STACS\u201908) for partial cover this implies that our bound is essentially best possible among algorithms that utilize an LMP algorithm for the Lagrangian relaxation as a black box. In addition to that, we argue by a more involved lower bound construction that even using the LMP algorithm by Byrka et al. in a <jats:italic>non-black-box<\/jats:italic> fashion could not beat the factor 4\/3 \u22c5 <jats:italic>r<\/jats:italic> when the tree merging step relies only on the solutions output by the LMP algorithm.<\/jats:p>","DOI":"10.1007\/s00224-020-09965-w","type":"journal-article","created":{"date-parts":[[2020,2,3]],"date-time":"2020-02-03T11:04:01Z","timestamp":1580727841000},"page":"626-644","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","volume":"64","author":[{"given":"Jaros\u0142aw","family":"Byrka","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2912-099X","authenticated-orcid":false,"given":"Mateusz","family":"Lewandowski","sequence":"additional","affiliation":[]},{"given":"Joachim","family":"Spoerhase","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,2,3]]},"reference":[{"issue":"3","key":"9965_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 + \u03b5)-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":"9965_CR2","doi-asserted-by":"publisher","unstructured":"Bateni, M., Hajiaghayi, M., Liaghat, V.: Improved approximation algorithms for (budgeted) node-weighted Steiner problems. In: Proc. 40th International Colloquium on Automata, Languages, and Programming (ICALP\u201913), pp 81\u201392 (2013), https:\/\/doi.org\/10.1007\/978-3-642-39206-1_8","DOI":"10.1007\/978-3-642-39206-1_8"},{"key":"9965_CR3","doi-asserted-by":"publisher","unstructured":"Berman, P., Yaroslavtsev, G.: Primal-dual approximation algorithms for node-weighted network design in planar graphs. In: Proc. 15th International Workshop on Approximation, Randomization, and Combinatorial Optimization (APPROX\u201912), pp 50\u201360 (2012). https:\/\/doi.org\/10.1007\/978-3-642-32512-0_5","DOI":"10.1007\/978-3-642-32512-0_5"},{"key":"9965_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: Proc. 15th Scandinavian symposium and workshops on algorithm theory (SWAT\u201916), pp 2:1\u20132:14 (2016). https:\/\/doi.org\/10.4230\/LIPIcs.SWAT.2016.2","DOI":"10.4230\/LIPIcs.SWAT.2016.2"},{"key":"9965_CR5","doi-asserted-by":"publisher","unstructured":"Chekuri, C., Ene, A., Vakilian, A.: Node-weighted network design in planar and minor-closed families of graphs. In: Proc. 39th International Colloquium on Automata, Languages, and Programming (ICALP\u201912), pp 206\u2013217 (2012), https:\/\/doi.org\/10.1007\/978-3-642-31594-7_18","DOI":"10.1007\/978-3-642-31594-7_18"},{"key":"9965_CR6","doi-asserted-by":"publisher","unstructured":"Chekuri, C., Ene, A., Vakilian, A.: Prize-collecting survivable network design in node-weighted graphs. In: Proc. 15th International Workshop on Approximation, Randomization, and Combinatorial Optimization (APPROX\u201912), pp 98\u2013109 (2012), https:\/\/doi.org\/10.1007\/978-3-642-32512-0_9","DOI":"10.1007\/978-3-642-32512-0_9"},{"issue":"2","key":"9965_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":"9965_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. Algor. 10(3), 13,1\u201313,20 (2014). https:\/\/doi.org\/10.1145\/2601070","journal-title":"ACM Trans. Algor."},{"key":"9965_CR9","doi-asserted-by":"publisher","unstructured":"Garg, N.: A 3-approximation for the minimum tree spanning k vertices. In: Proc. 37th Annual Symposium on Foundations of Computer Science (FOCS\u201996), pp 302\u2013309 (1996). https:\/\/doi.org\/10.1109\/SFCS.1996.548489","DOI":"10.1109\/SFCS.1996.548489"},{"key":"9965_CR10","doi-asserted-by":"publisher","unstructured":"Garg, N.: Saving an epsilon: A 2-approximation for the k-MST problem in graphs. In: Proc. 37th Annual ACM Symposium on Theory of Computing (STOC\u201905), pp 396\u2013402 (2005). https:\/\/doi.org\/10.1145\/1060590.1060650","DOI":"10.1145\/1060590.1060650"},{"issue":"2","key":"9965_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":"9965_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":"9965_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":"9965_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: Proc. 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201913), pp 568\u2013577 (2013), https:\/\/doi.org\/10.1109\/FOCS.2013.67","DOI":"10.1109\/FOCS.2013.67"},{"key":"9965_CR15","doi-asserted-by":"publisher","unstructured":"Mestre, J.: Lagrangian relaxation and partial cover. In: Proc. 25th Annual Symposium on Theoretical Aspects of Computer Science (STACS\u201908), pp 539\u2013550 (2008). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2008.1315","DOI":"10.4230\/LIPIcs.STACS.2008.1315"},{"key":"9965_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":"9965_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":"9965_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-25 January 1994, Arlington, Virginia, pp 546\u2013555 (1994)"},{"key":"9965_CR19","unstructured":"Sadeghabad, S.: Sina: Node-weighted prize-collecting Steiner tree and applications. Master\u2019s thesis (2013)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-09965-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-020-09965-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-09965-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,2]],"date-time":"2021-02-02T00:12:33Z","timestamp":1612224753000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-020-09965-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,3]]},"references-count":19,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,5]]}},"alternative-id":["9965"],"URL":"https:\/\/doi.org\/10.1007\/s00224-020-09965-w","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2020,2,3]]},"assertion":[{"value":"3 February 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}