TY - GEN
T1 - An LMP O(log n)-approximation algorithm for nodeweighted prize collecting steiner tree
AU - Könemann, Jochen
AU - Sadeghian, Sina
AU - Sanità, Laura
PY - 2013
Y1 - 2013
N2 - In the node-weighted prize-collecting Steiner tree problem (NW-PCST) we are given an undirected graph G = (V,E), non-negative costs c(v) and penalties π(v) for each v ∈ 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.
AB - In the node-weighted prize-collecting Steiner tree problem (NW-PCST) we are given an undirected graph G = (V,E), non-negative costs c(v) and penalties π(v) for each v ∈ 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.
KW - Approximation algorithms
KW - Lagrangean multiplier preserving
KW - Node-weighted steiner trees
KW - Prize-collecting problems
UR - http://www.scopus.com/inward/record.url?scp=84893515069&partnerID=8YFLogxK
U2 - 10.1109/FOCS.2013.67
DO - 10.1109/FOCS.2013.67
M3 - Conference contribution
AN - SCOPUS:84893515069
SN - 9780769551357
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 568
EP - 577
BT - Proceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013
T2 - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013
Y2 - 27 October 2013 through 29 October 2013
ER -