Bottleneck traveling salesman problem

[1] It was first formulated by Gilmore & Gomory (1964) with some additional constraints, and in its full generality by Garfinkel & Gilbert (1978).

The decision problem version of this, "for a given length x is there a Hamiltonian cycle in a graph G with no edge longer than x?

The maximum scatter traveling salesman problem is another variation of the traveling salesman problem in which the goal is to find a Hamiltonian cycle that maximizes the minimum edge length rather than minimizing the maximum length.

It can be translated into an instance of the bottleneck TSP problem by negating all edge lengths (or, to keep the results positive, subtracting them all from a large enough constant).

[1] If the graph is a metric space then there is an efficient approximation algorithm that finds a Hamiltonian cycle with maximum edge weight being no more than twice the optimum.

An approximation with ratio better than 2 in this metric space could be used to determine whether the original graph contains a Hamiltonian cycle, an NP-complete problem.