Bottleneck traveling salesman problem

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.[1]

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.[1]

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.[2]

See also

References

  1. 1 2 Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A2.3: ND24, pg.212.
  2. ↑ R. Garey Parker and Ronald L. Rardin (1984). "Guaranteed performance heuristics for the bottleneck traveling salesman problem". Operations Research Letters. 2(6):269–272
This article is issued from Wikipedia - version of the Monday, August 27, 2012. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.