09.04.2013

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.