Bottleneck traveling salesman problem

Last updated October 12, 2020

The Bottleneck traveling salesman problem (bottleneck TSP) is a problem in discrete or combinatorial optimization. The problem is to find the Hamiltonian cycle in a weighted graph which minimizes the weight of the most weighty edge of the cycle.^[1] It was first formulated by Gilmore & Gomory (1964) with some additional constraints, and in its full generality by Garfinkel & Gilbert (1978).^[1]^[2]^[3]

Complexity

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. NP-completeness follows immediately by a reduction from the problem of finding a Hamiltonian cycle.^[4]

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 $n i$ where $n$ is the number of vertices in the graph and $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 $O (n 22 n)$ .^[1]

Alternatively, the problem can be solved by performing a binary search or sequential search for the smallest $x$ such that the subgraph of edges of weight at most $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.^[1]

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

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 square 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 for metric spaces, its Hamiltonian cycle has edges of weight at most $2 θ$ .^[5]^[6]

This approximation ratio is best possible. For, any unweighted graph can be transformed into a metric space by setting its edge weights to $1$ and setting the distance between all nonadjacent pairs of vertices to $2$ . An approximation with ratio better than $2$ in this metric space could be used to determine whether the original graph contains a Hamiltonian cycle, an NP-complete problem.^[6]

Without the assumption that the input is a metric space, no finite approximation ratio is possible.^[1]

Related Research Articles

The travelling salesman problem 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 city exactly once and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in theoretical computer science and operations research.

In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path or a Hamiltonian cycle exists in a given graph. Both problems are NP-complete.

In theoretical computer science, the subgraph isomorphism problem is a computational task in which two graphs G and H are given as input, and one must determine whether G contains a subgraph that is isomorphic to H. Subgraph isomorphism is a generalization of both the maximum clique problem and the problem of testing whether a graph contains a Hamiltonian cycle, and is therefore NP-complete. However certain other cases of subgraph isomorphism may be solved in polynomial time.

The Steiner tree problem, or minimum Steiner tree problem, named after Jakob Steiner, is an umbrella term for a class of problems in combinatorial optimization. While Steiner tree problems may be formulated in a number of settings, they all require an optimal interconnect for a given set of objects and a predefined objective function. One well-known variant, which is often used synonymously with the term Steiner tree problem, is the Steiner tree problem in graphs. Given an undirected graph with non-negative edge weights and a subset of vertices, usually referred to as terminals, the Steiner tree problem in graphs requires a tree of minimum weight that contains all terminals. Further well-known variants are the Euclidean Steiner tree problem and the rectilinear minimum Steiner tree problem.

In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems with provable guarantees on the distance of the returned solution to the optimal one. Approximation algorithms naturally arise in the field of theoretical computer science as a consequence of the widely believed P ≠ NP conjecture. Under this conjecture, a wide class of optimization problems cannot be solved exactly in polynomial time. The field of approximation algorithms, therefore, tries to understand how closely it is possible to approximate optimal solutions to such problems in polynomial time. In an overwhelming majority of the cases, the guarantee of such algorithms is a multiplicative one expressed as an approximation ratio or approximation factor i.e., the optimal solution is always guaranteed to be within a (predetermined) multiplicative factor of the returned solution. However, there are also many approximation algorithms that provide an additive guarantee on the quality of the returned solution. A notable example of an approximation algorithm that provides both is the classic approximation algorithm of Lenstra, Shmoys and Tardos for scheduling on unrelated parallel machines.

The Euclidean minimum spanning tree or EMST is a minimum spanning tree of a set of n points in the plane, where the weight of the edge between each pair of points is the Euclidean distance between those two points. In simpler terms, an EMST connects a set of dots using lines such that the total length of all the lines is minimized and any dot can be reached from any other by following the lines.

The $k$ -minimum spanning tree problem, studied in theoretical computer science, asks for a tree of minimum cost that has exactly $k$ vertices and forms a subgraph of a larger graph. It is also called the $k$ -MST or edge-weighted $k$ -cardinality tree. Finding this tree is NP-hard, but it can be approximated to within a constant approximation ratio in polynomial time.

A feedback arc set (FAS) or feedback edge set is a set of edges which, when removed from the graph, leaves an acyclic graph. Put another way, it is a set containing at least one edge of every cycle in the graph. In graph theory, a directed graph may contain directed cycles, a closed one-way path of edges. In some applications, such cycles are undesirable, and we wish to eliminate them and obtain a directed acyclic graph (DAG). One way to do this is simply to drop edges from the graph to break the cycles.

In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. Any cut determines a cut-set, the set of edges that have one endpoint in each subset of the partition. These edges are said to cross the cut. In a connected graph, each cut-set determines a unique cut, and in some cases cuts are identified with their cut-sets rather than with their vertex partitions.

The Christofides algorithm or Christofides–Serdyukov algorithm is an algorithm for finding approximate solutions to the travelling salesman problem, on instances where the distances form a metric space . It is an approximation algorithm that guarantees that its solutions will be within a factor of 3/2 of the optimal solution length, and is named after Nicos Christofides and Anatoliy I. Serdyukov, who discovered it independently in 1976.

In graph theory and theoretical computer science, the longest path problem is the problem of finding a simple path of maximum length in a given graph. A path is called simple if it does not have any repeated vertices; the length of a path may either be measured by its number of edges, or by the sum of the weights of its edges. In contrast to the shortest path problem, which can be solved in polynomial time in graphs without negative-weight cycles, the longest path problem is NP-hard and the decision version of the problem, which asks whether a path exists of at least some given length, is NP-complete. This means that the decision problem cannot be solved in polynomial time for arbitrary graphs unless P = NP. Stronger hardness results are also known showing that it is difficult to approximate. However, it has a linear time solution for directed acyclic graphs, which has important applications in finding the critical path in scheduling problems.

For a graph, a maximum cut is a cut whose size is at least the size of any other cut. That is, it is a partition of the graph's vertices into two complementary sets S and T, such that the number of edges between the set S and the set T is as large as possible. The problem of finding a maximum cut in a graph is known as the Max-Cut Problem.

Clustering is the problem of partitioning data points into groups based on their similarity. Correlation clustering provides a method for clustering a set of objects into the optimum number of clusters without specifying that number in advance.

In computational geometry and computer science, the minimum-weight triangulation problem is the problem of finding a triangulation of minimal total edge length. That is, an input polygon or the convex hull of an input point set must be subdivided into triangles that meet edge-to-edge and vertex-to-vertex, in such a way as to minimize the sum of the perimeters of the triangles. The problem is NP-hard for point set inputs, but may be approximated to any desired degree of accuracy. For polygon inputs, it may be solved exactly in polynomial time. The minimum weight triangulation has also sometimes been called the optimal triangulation.

In computational complexity theory, a problem is NP-complete when:

A nondeterministic Turing machine can solve it in polynomial-time.
A deterministic Turing machine can solve it in large time complexity classes and can verify its solutions in polynomial time.
It can be used to simulate any other problem with similar solvability.

In graph theory, a branch of mathematics, a cycle basis of an undirected graph is a set of simple cycles that forms a basis of the cycle space of the graph. That is, it is a minimal set of cycles that allows every even-degree subgraph to be expressed as a symmetric difference of basis cycles.

In mathematics, the minimum k-cut, is a combinatorial optimization problem that requires finding a set of edges whose removal would partition the graph to at least k connected components. These edges are referred to as k-cut. The goal is to find the minimum-weight k-cut. This partitioning can have applications in VLSI design, data-mining, finite elements and communication in parallel computing.

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 G is a 2-vertex-connected graph, then the square of G is Hamiltonian. it is named after Herbert Fleischner, who published its proof in 1974.

In computational complexity theory, a gap reduction is a reduction to a particular type of decision problem, known as a c-gap problem. Such reductions provide information about the hardness of approximating solutions to optimization problems. In short, a gap problem refers to one wherein the objective is to distinguish between cases where the best solution is above one threshold from cases where the best solution is below another threshold, such that the two thresholds have a gap in between. Gap reductions can be used to demonstrate inapproximability results, as if a problem may be approximated to a better factor than the size of gap, then the approximation algorithm can be used to solve the corresponding gap problem.

References

1 2 3 4 5 6 Kabadi, Santosh N.; Punnen, Abraham P. (2007), "The bottleneck TSP", in Gutin, Gregory; Punnen, Abraham P. (eds.), The Traveling Salesman Problem and Its Variations, Combinatorial Optimization, Springer, pp. 697–735, doi:10.1007/0-306-48213-4_15 .
↑ Gilmore, P. C.; Gomory, R. E. (1964), "Sequencing a one state-variable machine: A solvable case of the traveling salesman problem", Oper. Res., 12 (5): 655–679, doi:10.1287/opre.12.5.655, JSTOR 167772 .
↑ Garfinkel, R. S.; Gilbert, K. C. (1978), "The bottleneck traveling salesman problem: Algorithms and probabilistic analysis", Journal of the ACM , 25 (3): 435–448, doi:10.1145/322077.322086, S2CID 12062434 .
↑ Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness , W.H. Freeman, A2.3: ND24, p. 212, ISBN 0-7167-1045-5 .
↑ Parker, R. Garey; Rardin, Ronald L. (1984), "Guaranteed performance heuristics for the bottleneck traveling salesman problem", Operations Research Letters, 2 (6): 269–272, doi:10.1016/0167-6377(84)90077-4 .
1 2 Hochbaum, Dorit S.; Shmoys, David B. (May 1986), "A unified approach to approximation algorithms for bottleneck problems", Journal of the ACM, New York, NY, USA: ACM, 33 (3): 533–550, doi:10.1145/5925.5933, S2CID 17975253 .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[kp07-1] 1 2 3 4 5 6 Kabadi, Santosh N.; Punnen, Abraham P. (2007), "The bottleneck TSP", in Gutin, Gregory; Punnen, Abraham P. (eds.), The Traveling Salesman Problem and Its Variations, Combinatorial Optimization, Springer, pp. 697–735, doi:10.1007/0-306-48213-4_15 .

[2] Gilmore, P. C.; Gomory, R. E. (1964), "Sequencing a one state-variable machine: A solvable case of the traveling salesman problem", Oper. Res., 12 (5): 655–679, doi:10.1287/opre.12.5.655, JSTOR 167772 .

[3] Garfinkel, R. S.; Gilbert, K. C. (1978), "The bottleneck traveling salesman problem: Algorithms and probabilistic analysis", Journal of the ACM , 25 (3): 435–448, doi:10.1145/322077.322086, S2CID 12062434 .

[gj-4] Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness , W.H. Freeman, A2.3: ND24, p. 212, ISBN 0-7167-1045-5 .

[5] Parker, R. Garey; Rardin, Ronald L. (1984), "Guaranteed performance heuristics for the bottleneck traveling salesman problem", Operations Research Letters, 2 (6): 269–272, doi:10.1016/0167-6377(84)90077-4 .

[hs-6] 1 2 Hochbaum, Dorit S.; Shmoys, David B. (May 1986), "A unified approach to approximation algorithms for bottleneck problems", Journal of the ACM, New York, NY, USA: ACM, 33 (3): 533–550, doi:10.1145/5925.5933, S2CID 17975253 .