An LMP O(log n)-approximation algorithm for nodeweighted prize collecting steiner tree

Jochen Könemann, Sina Sadeghian, Laura Sanità

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

17 Citations (Scopus)

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 languageEnglish
Title of host publicationProceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013
Pages568-577
Number of pages10
DOIs
Publication statusPublished - 2013
Externally publishedYes
Event2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013 - Berkeley, CA, United States
Duration: 27 Oct 201329 Oct 2013

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Conference

Conference2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013
CountryUnited States
CityBerkeley, CA
Period27/10/1329/10/13

Keywords

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

Fingerprint Dive into the research topics of 'An LMP O(log n)-approximation algorithm for nodeweighted prize collecting steiner tree'. Together they form a unique fingerprint.

Cite this