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:
“If the British prose style is Churchillian, America is the tobacco auctioneer, the barker; Runyon, Lardner, W.W., the traveling salesman who can sell the world the Brooklyn Bridge every day, can put anything over on you and convince you that tomatoes grow at the South Pole.”
—Ishmael Reed (b. 1938)
“[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)
“And just as there are no words for the surface, that is,
No words to say what it really is, that it is not
Superficial but a visible core, then there is
No way out of the problem of pathos vs. experience.”
—John Ashbery (b. 1927)