## 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(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.

Original language | English |
---|---|

Title of host publication | Proceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013 |

Pages | 568-577 |

Number of pages | 10 |

DOIs | |

Publication status | Published - 2013 |

Externally published | Yes |

Event | 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013 - Berkeley, CA, United States Duration: 27 Oct 2013 → 29 Oct 2013 |

### Conference

Conference | 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013 |
---|---|

Country/Territory | United States |

City | Berkeley, CA |

Period | 27/10/13 → 29/10/13 |

## Keywords

- Approximation algorithms
- Lagrangean multiplier preserving
- Node-weighted steiner trees
- Prize-collecting problems