The bottleneck traveling salesman problem and some variations

We present powerful heuristics for the bottleneck traveling salesman problem (BTSP) and closely related problems such as the maximum scatter traveling salesman problem (MSTSP) and the balanced traveling salesman problem, the later being a new problem which we in- troduce. Extensive computational results are presented. In particular, our BTSP heuristic produces provably optimal solutions for nearly every problem considered in a very rea- sonable running-time, both on problems with symmetric cost matrices and problems with asymmetric cost matrices. We also provide some theoretical analysis of lower bounds for the BTSP and introduce two new lower bound schemes for the BTSP on asymmetric cost matrices. We compliment this with new approximation algorithm with a guaranteed performance ratio for the BTSP on problems satisfying the triangle-inequality.