Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 2013 Copyright 2013 University of Bonn, Department of Computer Science, Abt. V
85345

25.09.2013

Prize Collecting Bottleneck Steiner Problems: A Combinatorial Approach
Fabian Hargesheimer
[Download PostScript] [Download PDF]

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.

Last Change: 11/05/14 at 11:02:05
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V