Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-APX-Reports 2013 Copyright 2013 Universität Bonn, Institut für Informatik, Abt. V
89144

09.04.2013

A Note on the Prize Collecting Bottleneck TSP and Related Problems
Fabian Hargesheimer
[Download PostScript] [Download PDF]

We design a 10/3 approximation algorithm for a penalty-based prize collecting version of the bottleneck TSP. In this variant of the TSP we look for a tour through a subset of vertices so that the maximum of (1.) the most expensive edge taken and (2.) the highest penalty for not visiting a node, is minimized. The presented algorithm combines linear programming and a rounding method with a heuristic approach for computing a bottleneck optimal tour.

Last Change: 11/05/14 at 11:04:20
 English
Universität Bonn -> Institut für Informatik -> Abteilung V