Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 2013 Copyright 2013 Universität Bonn, Institut für Informatik, 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
 English
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope