Title :
An LMP O(log n)-Approximation Algorithm for Node Weighted Prize Collecting Steiner Tree
Author :
Konemann, Jochen ; Sadeghian, S. ; Sanita, Laura
Author_Institution :
Combinatorics & Optimization, Univ. of Waterloo, Waterloo, ON, Canada
Abstract :
In the node-weighted prize-collecting Steiner tree problem (NW-PCST) we are given an undirected graph G = (V, E), non-negative costs c(u) and penalties π(u) for each u ∈ V . The goal is to find a tree T that minimizes the total cost of the vertices spanned by T plus the total penalty of vertices not in T. This problem is well-known to be set-cover hard to approximate. Moss and Rabani (STOC´01) presented a primal-dual Lagrangean-multiplier-preserving O(ln |V |)-approximation algorithm for this problem. We show a serious problem with the algorithm, and present a new, fundamentally different primal-dual method achieving the same performance guarantee. Our algorithm introduces several novel features to the primal-dual method that may be of independent interest.
Keywords :
computational complexity; graph theory; LMP O(log n)-approximation algorithm; NW-PCST; node weighted prize collecting steiner tree; nonnegative costs; primal-dual Lagrangean-multiplier-preserving O(ln |V|)-approximation algorithm; set-cover hard; undirected graph; Algorithm design and analysis; Approximation algorithms; Approximation methods; Joining processes; Linear programming; Standards; Steiner trees; Lagrangean multiplier preserving; Node-weighted Steiner trees; approximation algorithms; prize-collecting problems;
Conference_Titel :
Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on
Conference_Location :
Berkeley, CA
DOI :
10.1109/FOCS.2013.67