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)
“[Oliver North is a] document-shredding, Constitution-trashing, Commander in Chief-bashing, Congress-thrashing, uniform-shaming, Ayatollah-loving, arms-dealing, criminal-protecting, résumé-enhancing, Noriega-coddling, Social
Security-threatening, public school-denigrating, Swiss-banking-law-breaking, letter-faking, self-serving, election-losing, snake-oil salesman who can’t tell the difference between the truth and a lie.”
—Charles S. Robb (b. 1939)
“Like the effects of industrial pollution ... the AIDS crisis is evidence of a world in which nothing important is regional, local, limited; in which everything that can circulate does, and every problem is, or is destined to become, worldwide.”
—Susan Sontag (b. 1933)