Tong Zhang, G.H. Golub, et al.
Linear Algebra and Its Applications
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 article, 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 nondecreasing 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 by Nagarajan et al. [2008]. We further generalize our results for element-connectivity and node-connectivity. © 2012 ACM.
Tong Zhang, G.H. Golub, et al.
Linear Algebra and Its Applications
Daniel J. Costello Jr., Pierre R. Chevillat, et al.
ISIT 1997
Heinz Koeppl, Marc Hafner, et al.
BMC Bioinformatics
Sankar Basu
Journal of the Franklin Institute