25.09.2013

We design a purely combinatorial 2-approximation algorithm for the Prize Collecting Bottleneck k-STP, which arises naturally in several network design problems. Our algorithm is optimal in the sense that it matches the approximability lower bound of the non-prize collecting variant of the problem. We also consider the case of an unbounded number of Steiner nodes and show exact solutions for the Penalty- and Quota Bottleneck Steiner Tree Problem. Finally, we introduce a more powerful model in the form of Prize Collecting Steiner Forest where prizes are vectors, representing networks where nodes have different values to different subnets. We design extensions for our previous algorithms yielding exact solutions for both Penalty- and Quota Bottleneck Steiner Forests using this extended model.