The Bottleneck traveling salesman problem (bottleneck TSP) is a problem in discrete or combinatorial optimization. It is stated as follows: Find the Hamiltonian cycle in a weighted graph which minimizes the weight of the most weighty edge of the cycle.
The problem is known to be NP-hard. 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?", is NP-complete.
In an asymmetric bottleneck TSP, there are cases where the weight from node A to B is different from the weight from B to A (e. g. travel time between two cities with a traffic jam in one direction).
Euclidean bottleneck TSP, or planar bottleneck TSP, is the bottleneck TSP with the distance being the ordinary Euclidean distance. The problem still remains NP-hard, however many heuristics work better.
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.
Famous quotes containing the words traveling, salesman and/or problem:
“Mr. Alcott seems to have sat down for the winter. He has got Plato and other books to read. He is as large-featured and hospitable to traveling thoughts and thinkers as ever; but with the same Connecticut philosophy as ever, mingled with what is better. If he would only stand upright and toe the line!—though he were to put off several degrees of largeness, and put on a considerable degree of littleness. After all, I think we must call him particularly your man.”
—Henry David Thoreau (1817–1862)
“Nobody dast blame this man.... For a salesman, there is no rock bottom to the life. He don’t put a bolt to a nut, he don’t tell you the law or give you medicine. He’s a man way out there in the blue, riding on a smile and a shoeshine. And when they start not smiling back—that’s an earthquake. And then you get yourself a couple of spots on your hat, and you’re finished. Nobody dast blame this man. A salesman is got to dream, boy. It comes with the territory.”
—Arthur Miller (b. 1915)
“It is part of the educator’s responsibility to see equally to two things: First, that the problem grows out of the conditions of the experience being had in the present, and that it is within the range of the capacity of students; and, secondly, that it is such that it arouses in the learner an active quest for information and for production of new ideas. The new facts and new ideas thus obtained become the ground for further experiences in which new problems are presented.”
—John Dewey (1859–1952)