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:
“A modern democracy is a tyranny whose borders are undefined; one discovers how far one can go only by traveling in a straight line until one is stopped.”
—Norman Mailer (b. 1923)
“[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)
“Most childhood problems don’t result from “bad” parenting, but are the inevitable result of the growing that parents and children do together. The point isn’t to head off these problems or find ways around them, but rather to work through them together and in doing so to develop a relationship of mutual trust to rely on when the next problem comes along.”
—Fred Rogers (20th century)