Approximation algorithms for node-weighted prize-collecting Steiner tree problems on planar graphs

DOI10.4230/LIPICS.SWAT.2016.2MaRDI QIDQ5369504zbMATH OpenOpenAlexFDO

Authors Jaroslaw Byrka, Mateusz Lewandowski, Carsten Moldenhauer

Publication date 17 October 2017

Full work available at URL https://arxiv.org/abs/1601.02481

zbMATH Keywords

approximation algorithmsLMPnode-weighted Steiner treeplanar graphsprimal-dual algorithm

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Abstract: We study the prize-collecting version of the Node-weighted Steiner Tree problem (NWPCST) restricted to planar graphs. We give a new primal-dual Lagrangian-multiplier-preserving (LMP) 3-approximation algorithm for planar NWPCST. We then show a ($2.88+epsilon$)-approximation which establishes a new best approximation guarantee for planar NWPCST. This is done by combining our LMP algorithm with a threshold rounding technique and utilizing the 2.4-approximation of Berman and Yaroslavtsev for the version without penalties. We also give a primal-dual 4-approximation algorithm for the more general forest version using techniques introduced by Hajiaghay and Jain.

Recommendations

• Primal-dual approximation algorithms for node-weighted Steiner forest on planar graphs
• Approximating node-weighted \(k\)-MST on planar graphs
• Primal-dual approximation algorithms for node-weighted Steiner forest on planar graphs
• Approximating node-weighted \(k\)-MST on planar graphs
• scientific article; zbMATH DE number 6783450

Cited in

(11)

• Primal-dual approximation algorithms for node-weighted Steiner forest on planar graphs
• An approximation algorithm for the group prize-collecting Steiner tree problem with submodular penalties
• Primal-dual approximation algorithms for node-weighted Steiner forest on planar graphs
• Primal-dual approximation algorithms for node-weighted network design in planar graphs
• Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs
• Improved approximation algorithms for (budgeted) node-weighted Steiner problems
• Node-weighted Steiner tree and group Steiner tree in planar graphs
• scientific article; zbMATH DE number 6783450 (Why is no real title available?)
• Approximating node-weighted \(k\)-MST on planar graphs
• Approximating node-weighted \(k\)-MST on planar graphs
• A 2-approximation for the \(k\)-prize-collecting Steiner tree problem

This page was built for publication: Approximation algorithms for node-weighted prize-collecting Steiner tree problems on planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5369504)