Name
Title | ||
|---|---|---|
An LMP O(log n)-Approximation Algorithm for Node Weighted Prize Collecting Steiner Tree |
Abstract | ||
|---|---|---|
In the node-weighted prize-collecting Steiner tree problem we are given an undirected graph G=(V, E), non-negative costs c(v) and penalties π(v) for each v in 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 Lagrange an-multiplier-preserving Õ(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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1109/FOCS.2013.67 | foundations of computer science |
Keywords | DocType | Volume |
non-negative cost,approximation algorithm,total cost,log n,serious problem,total penalty,independent interest,primal-dual method,lmp o,node-weighted prize-collecting steiner tree,steiner tree,primal-dual lagrange an-multiplier-preserving,different primal-dual method,node weighted prize collecting,computational complexity,graph theory | Conference | abs/1302.2127 |
ISSN | Citations | PageRank |
0272-5428 | 6 | 0.48 |
References | Authors | |
11 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jochen Könemann | 1 | 158 | 9.98 |
| Sina Sadeghian | 2 | 6 | 0.48 |
| Laura Sanità | 3 | 257 | 18.36 |