Bottleneck traveling salesman problem

Last updated October 13, 2024

The Bottleneck traveling salesman problem (bottleneck TSP) is a problem in discrete or combinatorial optimization. The problem is to find the Hamiltonian cycle (visiting each node exactly once) in a weighted graph which minimizes the weight of the highest-weight 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 (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 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.

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. More generally, any edge-weighted undirected graph has a minimum spanning forest, which is a union of the minimum spanning trees for its connected components.

The Hamiltonian path problem is a topic discussed in the fields of complexity theory and graph theory. It decides if a directed or undirected graph, G, contains a Hamiltonian path, a path that visits every vertex in the graph exactly once. The problem may specify the start and end of the path, in which case the starting vertex s and ending vertex t must be identified.

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 combinatorial optimization problems are the travelling salesman problem ("TSP"), the minimum spanning tree problem ("MST"), and the knapsack problem. In many such problems, such as the ones previously mentioned, exhaustive search is not tractable, and so specialized algorithms that quickly rule out large parts of the search space or approximation algorithms must be resorted to instead.

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.

In combinatorial mathematics, 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 and minimizes the total weight of its edges. 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 $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.

In graph theory and graph algorithms, a feedback arc set or feedback edge set in a directed graph is a subset of the edges of the graph that contains at least one edge out of every cycle in the graph. Removing these edges from the graph breaks all of the cycles, producing an acyclic subgraph of the given graph, often called a directed acyclic graph. A feedback arc set with the fewest possible edges is a minimum feedback arc set and its removal leaves a maximum acyclic subgraph; weighted versions of these optimization problems are also used. If a feedback arc set is minimal, meaning that removing any edge from it produces a subset that is not a feedback arc set, then it has an additional property: reversing all of its edges, rather than removing them, produces a directed acyclic graph.

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 ; the latter discovered it independently in 1976.

<span class="mw-page-title-main">Maximum cut</span> Problem of finding a maximum cut in a graph

In 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 $S$ and $T$ is as large as possible. Finding such a cut is known as the max-cut problem.

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

It is a decision problem, meaning that for any input to the problem, the output is either "yes" or "no".
When the answer is "yes", this can be demonstrated through the existence of a short solution.
The correctness of each solution can be verified quickly and a brute-force search algorithm can find a solution by trying all possible solutions.
The problem can be used to simulate every other problem for which we can verify quickly that a solution is correct. In this sense, NP-complete problems are the hardest of the problems to which solutions can be verified quickly. If we could find solutions of some NP-complete problem quickly, we could quickly find the solutions of every other problem to which a given solution can be easily verified.

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, the metric $k$ -center problem or vertex k-center problem is a classical combinatorial optimization problem studied in theoretical computer science that is NP-hard. Given $n$ cities with specified distances, one wants to build $k$ warehouses in different cities and minimize the maximum distance of a city to a warehouse. In graph theory, this means finding a set of $k$ vertices for which the largest distance of any point to its closest vertex in the $k$ -set is minimum. The vertices must be in a metric space, providing a complete graph that satisfies the triangle inequality. It has application in facility location and clustering.

<span class="mw-page-title-main">Widest path problem</span> Path-finding using high-weight graph edges

In graph algorithms, the widest path problem is the problem of finding a path between two designated vertices in a weighted graph, maximizing the weight of the minimum-weight edge in the path. The widest path problem is also known as the maximum capacity path problem. It is possible to adapt most shortest path algorithms to compute widest paths, by modifying them to use the bottleneck distance instead of path length. However, in many cases even faster algorithms are possible.

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 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, vol. 12, Springer, pp. 697–735, doi:10.1007/0-306-48213-4_15, ISBN 978-0-387-44459-8 .
↑ 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, 33 (3), New York, NY, USA: ACM: 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, vol. 12, Springer, pp. 697–735, doi:10.1007/0-306-48213-4_15, ISBN 978-0-387-44459-8 .

[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, 33 (3), New York, NY, USA: ACM: 533–550, doi:10.1145/5925.5933, S2CID 17975253 .

[1]

[2]

[3]

[4]

[5]

[6]