Editing Bottleneck traveling salesman problem

The '''Bottleneck traveling salesman problem''' ('''bottleneck TSP''') is a problem in [[discrete optimization|discrete]] or [[combinatorial optimization]].  The problem is to find the [[Hamiltonian path|Hamiltonian cycle]] (visiting each node exactly once) in a [[weighted graph]] which minimizes the weight of the highest-weight [[Edge (graph theory)|edge]] of the cycle.<ref name="kp07">{{citation
 | last1 = Kabadi | first1 = Santosh N.
 | last2 = Punnen | first2 = Abraham P.
 | editor1-last = Gutin | editor1-first = Gregory
 | editor2-last = Punnen | editor2-first = Abraham P.
 | contribution = The bottleneck TSP
 | doi = 10.1007/0-306-48213-4_15
 | pages = 697–735
 | publisher = Springer
 | series = Combinatorial Optimization
 | title = The Traveling Salesman Problem and Its Variations
 | year = 2007| volume = 12
 | isbn = 978-0-387-44459-8
 }}.</ref> It was first formulated by {{harvtxt|Gilmore|Gomory|1964}} with some additional constraints, and in its full generality by {{harvtxt|Garfinkel|Gilbert|1978}}.<ref name="kp07"/><ref>{{citation
 | last1 = Gilmore | first1 = P. C.
 | last2 = Gomory | first2 = R. E. | author2-link = Ralph E. Gomory
 | doi = 10.1287/opre.12.5.655
 | journal = Oper. Res.
 | jstor = 167772
 | pages = 655–679
 | title = Sequencing a one state-variable machine: A solvable case of the traveling salesman problem
 | volume = 12
 | year = 1964| issue = 5
 }}.</ref><ref>{{citation
 | last1 = Garfinkel | first1 = R. S.
 | last2 = Gilbert | first2 = K. C.
 | doi = 10.1145/322077.322086
 | issue = 3
 | journal = [[Journal of the ACM]]
 | pages = 435–448
 | title = The bottleneck traveling salesman problem: Algorithms and probabilistic analysis
 | volume = 25
 | year = 1978| s2cid = 12062434
 | doi-access = free
 }}.</ref>

==Complexity==
The problem is known to be [[NP-hard]]. The [[decision problem]] version of this, "for a given length {{mvar|x}} is there a Hamiltonian cycle in a graph {{mvar|G}} with no edge longer than {{mvar|x}}?", is [[NP-complete]]. NP-completeness follows immediately by a [[Reduction (complexity)|reduction]] from the problem of finding a Hamiltonian cycle.<ref name=gj>{{citation
 | last1 = Garey
 | first1 = Michael R.
 | author1-link = Michael R. Garey
 | last2 = Johnson
 | first2 = David S.
 | author2-link = David S. Johnson
 | isbn = 0-7167-1045-5
 | publisher = W.H. Freeman
 | title = [[Computers and Intractability: A Guide to the Theory of NP-Completeness]]
 | year = 1979
 | at = [https://archive.org/details/computersintract0000gare/page/ A2.3: ND24, p.&nbsp;212]
 }}.</ref>

==Algorithms==
Another reduction, from the bottleneck TSP to the usual TSP (where the goal is to minimize the sum of edge lengths), allows any algorithm for the usual TSP to also be used to solve the bottleneck TSP.
If the edge weights of  the bottleneck TSP are replaced by any other numbers that have the same relative order, then the bottleneck solution remains unchanged.
If, in addition, each number in the sequence exceeds the sum of all smaller numbers, then the bottleneck solution will also equal the usual TSP solution.
For instance, such a result may be attained by resetting each weight to {{math|''n''<sup>''i''</sup>}} where {{mvar|n}} is the number of vertices in the graph and {{mvar|i}} is the rank of the original weight of the edge in the sorted sequence of weights. For instance, following this transformation, the [[Held–Karp algorithm]] could be used to solve the bottleneck TSP in time {{math|''O''(''n''<sup>2</sup>2<sup>''n''</sup>)}}.<ref name="kp07"/>

Alternatively, the problem can be solved by performing a [[binary search]] or [[sequential search]] for the smallest {{mvar|x}} such that the subgraph of edges of weight at most {{mvar|x}} has a Hamiltonian cycle. This method leads to solutions whose running time is only a logarithmic factor larger than the time to find a Hamiltonian cycle.<ref name="kp07"/>

==Variations==

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).

The '''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 for it than for other distance functions.

The '''maximum scatter traveling salesman problem''' is another variation of the traveling salesman problem in which the goal is to find a Hamiltonian cycle that maximizes the minimum edge length rather than minimizing the maximum length. Its applications include the analysis of medical images, and the scheduling of metalworking steps in aircraft manufacture to avoid heat buildup from steps that are nearby in both time and space. It can be translated into an instance of the bottleneck TSP problem by negating all edge lengths (or, to keep the results positive, subtracting them all from a large enough constant). However, although this transformation preserves the optimal solution, it does not preserve the quality of approximations to that solution.<ref name="kp07"/>

==Metric approximation algorithm==
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.
This result follows by [[Fleischner's theorem]], that the [[Graph power|square]] of a [[k-vertex-connected graph|2-vertex-connected graph]] always contains a Hamiltonian cycle. It is easy to find a threshold value {{mvar|θ}}, the smallest value such that the edges of weight {{mvar|θ}} form a 2-connected graph. Then {{mvar|θ}} provides a valid lower bound on the bottleneck TSP weight, for the bottleneck TSP is itself a 2-connected graph and necessarily contains an edge of weight at least {{mvar|θ}}. However, the square of the subgraph of edges of weight at most {{mvar|θ}} is Hamiltonian. By the [[triangle inequality]] for metric spaces, its Hamiltonian cycle has edges of weight at most {{math|2''θ''}}.<ref>{{citation
 | last1 = Parker | first1 = R. Garey
 | last2 = Rardin | first2 = Ronald L.
 | doi = 10.1016/0167-6377(84)90077-4
 | issue = 6
 | journal = Operations Research Letters
 | pages = 269–272
 | title = Guaranteed performance heuristics for the bottleneck traveling salesman problem
 | volume = 2
 | year = 1984}}.</ref><ref name="hs">{{citation
 | last1 = Hochbaum | first1 = Dorit S. | author1-link = Dorit S. Hochbaum
 | last2 = Shmoys | first2 = David B. | author2-link = David Shmoys
 | date = May 1986
 | doi = 10.1145/5925.5933
 | issue = 3
 | journal = Journal of the ACM
 | location = New York, NY, USA
 | pages = 533–550
 | publisher = ACM
 | title = A unified approach to approximation algorithms for bottleneck problems
 | url = https://www.researchgate.net/publication/220430962
 | volume = 33| s2cid = 17975253 }}.</ref>

This approximation ratio is best possible. For, any unweighted graph can be transformed into a metric space by setting its edge weights to {{math|1}} and setting the distance between all nonadjacent pairs of vertices to {{math|2}}. An approximation with ratio better than {{math|2}} in this metric space could be used to determine whether the original graph contains a Hamiltonian cycle, an NP-complete problem.<ref name="hs"/>

Without the assumption that the input is a metric space, no finite approximation ratio is possible.<ref name="kp07"/>

==See also==
*[[Travelling salesman problem]] 

== References ==
{{reflist}}

[[Category:Combinatorial optimization]]
[[Category:Graph algorithms]]
[[Category:Hamiltonian paths and cycles]]
[[Category:NP-complete problems]]