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:
“Somewhere someone is traveling furiously toward you,
At incredible speed, traveling day and night....”
—John Ashbery (b. 1927)
“[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)
“[How] the young . . . can grow from the primitive to the civilized, from emotional anarchy to the disciplined freedom of maturity without losing the joy of spontaneity and the peace of self-honesty is a problem of education that no school and no culture have ever solved.”
—Leontine Young (20th century)