Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-APX-Reports 2013 Copyright 2013 University of Bonn, Department of Computer Science, 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
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V