Prize-collecting Steiner network problems

Mohammad Taghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz, Zeev Nutov

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations


In the Steiner Network problem we are given a graph G with edge-costs and connectivity requirements ruv between node pairs u,v. The goal is to find a minimum-cost subgraph H of G that contains ruv edge-disjoint paths for all u,v ∈ V. In Prize-Collecting Steiner Network problems we do not need to satisfy all requirements, but are given a penalty function for violating the connectivity requirements, and the goal is to find a subgraph H that minimizes the cost plus the penalty. The case when ruv ∈ {0,1} is the classic Prize-Collecting Steiner Forest problem. In this paper we present a novel linear programming relaxation for the Prize-Collecting Steiner Network problem, and by rounding it, obtain the first constant-factor approximation algorithm for submodular and monotone non-decreasing penalty functions. In particular, our setting includes all-or-nothing penalty functions, which charge the penalty even if the connectivity requirement is slightly violated; this resolves an open question posed in [SSW07]. We further generalize our results for element-connectivity and node-connectivity.

Original languageEnglish (US)
Title of host publicationInteger Programming and Combinatorial Optimization - 14th International Conference, IPCO 2010, Proceedings
PublisherSpringer Verlag
Number of pages14
ISBN (Print)3642130356, 9783642130359
StatePublished - 2010
Event14th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2010 - Lausanne, China
Duration: Jun 9 2010Jun 11 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6080 LNCS


Other14th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2010

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Prize-collecting Steiner network problems'. Together they form a unique fingerprint.

Cite this