The Bottleneck traveling salesman problem (bottleneck TSP) is a problem in
discrete
Discrete may refer to:
*Discrete particle or quantum in physics, for example in quantum theory
* Discrete device, an electronic component with just one circuit element, either passive or active, other than an integrated circuit
*Discrete group, a ...
or
combinatorial optimization
Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combi ...
. The problem is to find the
Hamiltonian cycle
In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...
(visiting each node exactly once) in a
weighted graph
This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.
Symbols
A
B
...
which minimizes the weight of the highest-weight
edge
Edge or EDGE may refer to:
Technology Computing
* Edge computing, a network load-balancing system
* Edge device, an entry point to a computer network
* Adobe Edge, a graphical development application
* Microsoft Edge, a web browser developed by ...
of the cycle.
[.] It was first formulated by with some additional constraints, and in its full generality by .
Complexity
The problem is known to be
NP-hard
In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
. The
decision problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whethe ...
version of this, "for a given length is there a Hamiltonian cycle in a graph with no edge longer than ?", is
NP-complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...
. NP-completeness follows immediately by a
reduction from the problem of finding a Hamiltonian cycle.
[.]
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 where is the number of vertices in the graph and 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
The Held–Karp algorithm, also called Bellman–Held–Karp algorithm, is a dynamic programming algorithm proposed in 1962 independently by Bellman and by Held and Karp to solve the traveling salesman problem (TSP), in which the input is a distan ...
could be used to solve the bottleneck TSP in time .
Alternatively, the problem can be solved by performing a
binary search
In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the m ...
or
sequential search
In computer science, a linear search or sequential search is a method for finding an element within a list. It sequentially checks each element of the list until a match is found or the whole list has been searched.
A linear search runs in at ...
for the smallest such that the subgraph of edges of weight at most 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.
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
In mathematics, the Euclidean distance between two points in Euclidean space is the length of a line segment between the two points.
It can be calculated from the Cartesian coordinates of the points using the Pythagorean theorem, therefor ...
. 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.
Metric approximation algorithm
If the graph is a
metric space
In mathematics, a metric space is a set together with a notion of ''distance'' between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general settin ...
then there is an efficient
approximation algorithm
In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solu ...
that finds a Hamiltonian cycle with maximum edge weight being no more than twice the optimum.
This result follows by
Fleischner's theorem
In graph theory, a branch of mathematics, Fleischner's theorem gives a sufficient condition for a graph to contain a Hamiltonian cycle. It states that, if is a 2-vertex-connected graph, then the square of is Hamiltonian. it is named after He ...
, that the
square
In Euclidean geometry, a square is a regular quadrilateral, which means that it has four equal sides and four equal angles (90-degree angles, π/2 radian angles, or right angles). It can also be defined as a rectangle with two equal-length adj ...
of a
2-vertex-connected graph always contains a Hamiltonian cycle. It is easy to find a threshold value , the smallest value such that the edges of weight form a 2-connected graph. Then 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 . However, the square of the subgraph of edges of weight at most is Hamiltonian. By the
triangle inequality
In mathematics, the triangle inequality states that for any triangle, the sum of the lengths of any two sides must be greater than or equal to the length of the remaining side.
This statement permits the inclusion of degenerate triangles, but ...
for metric spaces, its Hamiltonian cycle has edges of weight at most .
[.][.]
This approximation ratio is best possible. For, any unweighted graph can be transformed into a metric space by setting its edge weights to and setting the distance between all nonadjacent pairs of vertices to . An approximation with ratio better than in this metric space could be used to determine whether the original graph contains a Hamiltonian cycle, an NP-complete problem.
Without the assumption that the input is a metric space, no finite approximation ratio is possible.
See also
*
Travelling salesman problem
The travelling salesman problem (also called the travelling salesperson problem or TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each cit ...
References
{{reflist
Combinatorial optimization
Graph algorithms
Hamiltonian paths and cycles