Consider the traveling salesman problem where the distance between two cities A and B is an integrable function of the y-coordinate of A and the x-coordinate of B. This problem finds important applications in operations management and combinatorial optimization. Gilmore and Gomory gave a polynomial time algorithm for this problem. In the bottleneck variant of this problem (BP), we seek a tour that minimizes the maximum distance between any two consecutive cities. For BP, Gilmore and Gomory state that they “do not yet know how to solve the problem for general integrable functions”. We show that BP is strongly NP-complete. Also, we use this reduction to provide a method for proving NP-completeness of other combinatorial problems.
