2013/02/08 by Jochen Könemann, Sina Sadeghian, Könemann, Jochen +3 · 1 citation
Computer Science · Economics, Econometrics and Finance · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.1302.2127
openalex publication_date 2013/02/08 · openalex created_date 2022/10/02 · openalex updated_date 2026/07/28
In the node-weighted prize-collecting Steiner tree problem (NW-PCST) we are\ngiven an undirected graph G=(V,E), non-negative costs c(v) and penalties\n\π(v) for each v \∈ V. The goal is to find a tree T that minimizes the\ntotal cost of the vertices spanned by T plus the total penalty of vertices\nnot in T. This problem is well-known to be set-cover hard to approximate.\nMoss and Rabani (STOC'01) presented a primal-dual\nLagrangean-multiplier-preserving O(\ln |V|)-approximation algorithm for this\nproblem. We show a serious problem with the algorithm, and present a new,\nfundamentally different primal-dual method achieving the same performance\nguarantee. Our algorithm introduces several novel features to the primal-dual\nmethod that may be of independent interest.\n