Approximating node-weighted k-MST on planar graphs

Jarosław Byrka, Mateusz Lewandowski*, Joachim Spoerhase

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Abstract

We study the problem of finding a minimum weight connected subgraph spanning at least k vertices on planar, node-weighted graphs. We give a (4+ε) -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’16) and adopting an approach by Chudak et al. (Math. Prog. ’04) 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. ’06). More generally, our approach readily gives a(4/3.r+ε) -approximation on any graph class where the algorithm of Byrka et al. for the prize-collecting version gives an r-approximation. We argue that this can be interpreted as a generalization of an analogous result by Könemann et al. (Algorithmica ’11) for partial cover problems. Together with a lower bound construction by Mestre (STACS’08) 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 non-black-box fashion could not beat the factor 4/3.r when the tree merging step relies only on the solutions output by the LMP algorithm.

Original languageEnglish
Title of host publicationApproximation and Online Algorithms - 16th International Workshop, WAOA 2018, Revised Selected Papers
EditorsLeah Epstein, Thomas Erlebach
Pages87-101
Number of pages15
DOIs
Publication statusPublished - 1 Jan 2018
MoE publication typeA4 Article in a conference publication
EventWorkshop on Approximation and Online Algorithms - Helsinki, Finland
Duration: 23 Aug 201824 Aug 2018
Conference number: 16

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11312 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Workshop

WorkshopWorkshop on Approximation and Online Algorithms
Abbreviated titleWAOA
CountryFinland
CityHelsinki
Period23/08/201824/08/2018

Fingerprint

Dive into the research topics of 'Approximating node-weighted k-MST on planar graphs'. Together they form a unique fingerprint.

Cite this