Home/Blog/Data Science/Approximation algorithms and the metric TSP
Home/Blog/Data Science/Approximation algorithms and the metric TSP

Approximation algorithms and the metric TSP

15 min read
Jan 15, 2024
content
Approximation algorithms
TSP
Metric TSP
The approximation guarantee
The wow factor
A 2-approximation algorithm
Notation
Correctness and proof of a 2-approximation
An upper bound on the approximate solution
A lower bound on the optimum solution
Some concluding remarks

Become a Software Engineer in Months, Not Years

From your first line of code, to your first day on the job — Educative has you covered. Join 2M+ developers learning in-demand programming skills.

Computational problems that arise in the real world can be complex and unwieldy. They often need efficient solutions that must either be found or, if that’s not possible, some trade-off must be made. For some applications, an efficient algorithm that quickly arrives at a solution that’s not the best, but is ‘good enough’, is a happy compromise. Approximation algorithms are designed to provide efficient, but approximate solutions to hard problems. They’re different, though, from algorithms that purely rely on heuristics in that they’re accompanied by performance guarantees of how close they are to the best possible solution.

The overarching theme of approximation algorithms is to find a solution that may not necessarily be the best one, but that comes close to the best one with some kind of mathematical guarantee.

Approximation algorithms#

In this blog post, we cover the basic idea behind approximation algorithms and describe precisely what we mean by a mathematical guarantee accompanying an approximation algorithm. As a first example, we’ll cover what’s called a 22-approximation algorithm for a problem called the metric traveling salesperson problem.

Note: This blog post assumes that the reader is familiar with introductory level ideas in algorithms such as preorder traversals, and minimum spanning trees.

TSP#

The traveling salesperson problem (TSP) (also known as the traveling salesman problem) is a computational problem, that’s often narrated as the story of a traveling salesperson faced with the difficult task of planning a tour of nn cities with the smallest associated cost. The cost could be anything like the distance traveled between two cities, the traveling time, the traffic, the cost of fuel or some combination of these. The traveling salesperson wants to visit each city exactly once before returning to the city where the tour originated.

The story of the traveling salesperson can be abstracted away by representing the network of cities as a complete graph on nn vertices, with nonnegative edge costs. A complete graph is a graph in which there’s an edge joining each pair of vertices. By nonnegative edge costs, we mean that a nonnegative numeric value is associated with each edge. Couched in these graph theoretic terms, the problem then is to find a cycle in the complete graph on nn vertices such that each vertex is visited exactly once, and the total cost of all the edges in the tour is minimized.

Here’s an example of a complete graph on five vertices with numeric costs assigned to the edges. Observe how the tours shown on each slide have varying costs.

A complete graph with numeric edge costs
1 / 4
A complete graph with numeric edge costs

The TSP is an example of what are known as NP-hard optimization problems. This means there are no known efficient algorithms for solving the TSP. A brute-force solution would entail trying out all (n1)!/2(n-1)!/2 possibilities. Just to get a sense of how bad this is, if we take n=100n=100, the sheer number of possibilities considered by such an algorithm exceeds the number of atoms in the observable universe. So, as far as performance goes, employing such a brute-force solution is unacceptable for applications where nn is large and the responsiveness is important.

Metric TSP#

The problem may be hard, but the need for a solution is very real, as evident from the many services that assist with round-trip planning of delivery routes or tours. It’s not unusual, in research circles, to simplify a problem in the hopes of making progress that may ultimately lead to a solution for the more general problem. The simplified problem may be useful in itself as well.

One such simplification is a restricted version of the TSP called the metric TSP in which the cost function is required to obey the triangle inequality. The triangle inequality requires that in any cycle of three vertices and three edges, the sum of the costs of any two edges is at least the cost of the third edge. In this sense, the costs specified are like Euclidean distances, where the shortest distance between two points is a straight line.

The triangle inequality holds for the costs assigned to the edges of the cycle
The triangle inequality holds for the costs assigned to the edges of the cycle

It turns out that applying this restriction to the TSP makes life a little bit easier, and the additional structure is helpful in arriving at approximation algorithms for the metric TSP.

The approximation guarantee#

An optimization problem is a problem where the goal is to minimize or maximize a value. The value being minimized or maximized is called the objective value.

  • For the traveling salesperson problem, the cost of the tour is the objective value.
  • For a problem that requires maximization of profits, the profit is the objective value.

An approximation guarantee is a mathematical way to state how close the objective value of a solution, produced by an approximation algorithm, is to the objective value of the optimum solution. As we see below, the approximation guarantee is defined differently for maximization and minimization problems.

  • For a maximization problem, suppose that MM^* is the maximum objective value, but our algorithm produces a solution with objective value MM. Then the ratio MM\frac{M^*}{M} tells us how good our solution is relative to the best possible solution. For example, if the ratio is 10050=2\frac{100}{50} = 2 for an input, it tells us that our solution is twice as bad as the optimum solution for that input instance. This ratio is different for each problem instance. If there’s an upper bound ρ(n)\rho(n) on this ratio, so that for any problem instance of size nn,

    MMρ(n)\frac{M^*}{M} \leq \rho(n)

    then ρ(n)\rho(n) is said to be the approximation guarantee for the maximization problem where 0<MM0 < M \leq M^*. When ρ(n)\rho(n) is a constant, it’s written simply as ρ\rho.

    Note: If an objective value is allowed to be zero, it’s best to express this inequality in the following form to avoid a divide-by-zero situation.

    Mρ(n)MM^* \leq \rho(n)\cdot M

An example of how the numbers can appear on a real line,  for a maximization problem
An example of how the numbers can appear on a real line, for a maximization problem
  • For convenience, approximation guarantees are defined to be greater than or equal to 11. Because of this, the definition of an approximation guarantee is slightly different for minimization problems. The ratio under consideration is M/MM/M^* instead of M/MM^*/M, where MM^* is the minimum objective value. For a minimization problem, ρ(n)\rho(n) is the approximation guarantee, if

    MMρ(n)\frac{M}{M^*}\leq \rho(n)

    where 0<MM0 < M^* \leq M for any problem instance of size nn.

    Note: Once again if an objective value is allowed to be zero, it’s best to express the inequality in the following form to preclude the possibility of a division by zero.

    Mρ(n)MM \leq \rho(n)\cdot M^*

An example of how the numbers can appear on a real line, for a minimization problem
An example of how the numbers can appear on a real line, for a minimization problem

An algorithm which comes with the approximation guarantee ρ(n)\rho(n) is called a ρ(n)\rho(n)–approximation algorithm. This tells us that no matter which input of size nn is passed to our algorithm, it gives a solution which is guaranteed to be within a factor of ρ(n)\rho(n) of the optimum solution.

In this blog post, we’ll cover a 22-approximation algorithm for an optimization problem (the metric TSP problem). This means that on any input, the algorithm produces a solution that has a cost within a factor of 22 of the minimum cost.

The wow factor#

When designing an approximation algorithm, the first step is to come up with a polynomial-time algorithm that finds a solution (and not necessarily the best solution). The second step is figuring out an approximation guarantee.

Typically, the approximation guarantee is found by establishing a relationship of the optimum solution with some other entity, and then showing how that other entity is related to the approximate solution.

For example, as we’ll see below, the guarantee of the 22-approximation algorithm is arrived at by comparing both the cost of the approximate solution and the cost of the optimum solution to the cost of a minimum spanning tree (MST) of the graph under consideration.

It isn’t obvious, though, how one would come up with an approximation guarantee for an arbitrary approximation algorithm, since the upper bound on the ratio of MM and MM^* needs to be established for each conceivable input of size nn, and since MM^* is also unknown.

The wow factor in the design of approximation algorithms lies in this delicate work of art that fashions a mathematical guarantee out of what seems to be chaos and validates the hunch that led to the efficient solution in the first place.

Let’s see this in action for a 22-approximation solution for the metric TSP.

A 2-approximation algorithm#

Here’s a 22-approximation algorithm for the metric TSP:

  1. Given a complete weighted graph GG, pick any vertex vv as the root, and find a minimum spanning tree TT, using Prim’s algorithm.
  2. Compile a list LL of vertices encountered in a preorder traversal of TT.
  3. Return LL as a tour.

Since LL contains each vertex exactly once, it constitutes a tour where there’s an edge between each pair of consecutive vertices, and between the first and the last vertex.

Note: For clarity, in our illustrations and discussion below, we list the first vertex again at the end to highlight that this is a tour.

A complete graph with the cost function obeying the triangle inequality
1 / 4
A complete graph with the cost function obeying the triangle inequality

This algorithm is a polynomial-time algorithm because both Prim's algorithm and depth-first search (which is needed for a preorder traversal) are polynomial-time algorithms in the size of the input graph.

In the rest of this blog post, we argue that cost of the tour LL of the graph GG is at most twice the optimum cost of a traveling salesperson tour of GG.

Notation#

To discuss why the algorithm works as expected, we use the following notations to denote different costs.

  • MM denotes the cost of the tour LL produced by our algorithm.

  • MM^* denotes the minimum possible cost for a traveling salesperson tour of a given input graph.

  • The cost function is denoted by cc.

    • The notation c(u,v)c(u,v) denotes the cost associated with an edge (u,v)(u,v).
    • The notation c(T)c(T) is the cost (or the weight) of the MST TT produced by Prim’s algorithm. In general, the notation c(K)c(K) means the sum of costs of edges in KK.

Correctness and proof of a 2-approximation#

To prove that our algorithm is a 22-approximation, we want to show the following:

M2MM \leq 2 M^*

First we show how the weight c(T)c(T) of the MST TT is related to MM, and to MM^*, so we can use these two relationships to conclude that the approximation guarantee is 22.

An upper bound on the approximate solution#

Suppose we traverse a graph GG by walking along the edges of its minimum spanning tree TT. After visiting all the vertices of GG, we come back to the vertex where we started. In doing this, each edge of TT must be traversed in both directions. Suppose WW is the sequence of edges in the walk, then the cost of such a walk, c(W)c(W), would be twice the weight of TT as each edge of the MST TT is traversed twice.

c(W)=2c(T)  (1)c(W)=2c(T) \qquad \ldots \ \ (1)

Walking in graph G along the edges of the subgraph T
Walking in graph G along the edges of the subgraph T

When the walk WW is considered as a sequence of vertices, listed in the order in which they are visited, each vertex in the sequence appears one or more times depending on how many times it’s visited during the walk. For example, in the illustration above, WW consists of the following sequence of vertices (with repeating occurrences highlighted in red):

v2,v3,v5,v3,v1,v3,v2,v4,v2v_2, v_3, v_5, \red{v_3}, v_1, \red{v_3}, \red{v_2}, v_4, \red{v_2}

If we strike off all the repeat visits to each vertex, we end up retaining only the first visits to each vertex as we walk around along the edges of TT. Note that the sequence of first visits corresponds exactly to a preorder traversal of the minimum spanning tree TT. Since the first and the last vertex in a tour are identical, striking off all the repeat visits except for the last vertex of WW gets us exactly the tour returned by our algorithm. If we apply this to our example above, we get the following:

v2,v3,v5,v3,v1,v3,v2,v4,v2    v2,v3,v5,v1,v4,v2\begin{align*} & v_2, v_3, v_5, \cancel{\red{v_3}}, v_1, \cancel{\red{v_3}}, \cancel{\red{v_2}}, v_4, \red{v_2} \\ \implies & v_2, v_3, v_5, v_1, v_4, v_2 \end{align*}

Note that each time we strike off a vertex in WW, we bypass it, which results in lowering the cost of the resulting walk by the triangle inequality.

This means that the cost, MM, of the solution returned by our algorithm is at most c(W)c(W).

Mc(W)M \leq c(W)

As c(W)=2c(T)c(W)=2c(T), by Equation (1)(1) above, it implies the following:

M2c(T)  (2)M \leq 2 c(T) \qquad \ldots \ \ (2)

Repeating occurrences of a vertex in the walk highlighted in red
1 / 5
Repeating occurrences of a vertex in the walk highlighted in red

A lower bound on the optimum solution#

Let MM^* be the cost of a minimum travelling salesperson tour for a problem instance. Since the optimum tour is a cycle, removing an edge from it gets us a path PP on nn vertices. As the edge costs are nonnegative, the cost c(P)c(P) of the resulting path is at most the cost of the tour:

c(P)Mc(P) \leq M^*

Since PP contains all vertices of the graph GG, it is a spanning tree of GG. From this, we can infer that its cost is at least as much as that of the minimum spanning tree TT.

c(T)c(P)c(T) \le c(P)

Therefore,

c(T)c(P)M    c(T)M\begin{align*} c(T) &\le c(P)\leq M^*\\ \implies c(T) &\leq M^*\\ \end{align*}

Multiplying both sides by 22, we get

2c(T)2M  (3)\begin{align*} 2c(T) &\leq 2 M^* \qquad \ldots \ \ (3) \end{align*}

Putting the inequalities (2) and (3) together, we get

M2 c(T)2MM \leq 2\ c (T) \leq 2 M^*

In other words, we get

M2MM \leq 2 M^*

This establishes that the algorithm discussed here is a 22-approximation algorithm.

Some concluding remarks#

We showed a polynomial-time 22-approximation algorithm for the metric TSP. We proved the approximation guarantee in two steps that involved the following:

  • Bounding the cost of our approximate solution, from above, by twice the cost of an MST.
  • Bounding the cost of the optimum traveling salesperson tour, from below, by the cost of an MST.

There’s a better approximation algorithm for the metric TSP called the Christofides algorithm, which has an improved approximation guarantee of 3/23/2. In a paper presented at STOC 2021 (ACM Symposium on Theory of Computing), this approximation guarantee was (slightly) improved further.

It’s worth noting that it isn’t always straightforward to come up with a polynomial-time constant-approximation for an NP-hard problem. Indeed, it is well-known that no polynomial-time constant-approximation algorithm exists for the general traveling salesperson problem, unless P=NPP=NP.


There are other heuristic- based approaches for solving the TSP. If you are inclined towards exploring other techniques, you might be interested in this hands-on project by Educative, which helps you implement a probabilistic method called simulated annealing to arrive at an approximate solution to the TSP.


Frequently Asked Questions

What is metric TSP?

The metric TSP provides a way to solve the NP-hard Traveling Salesman Problem. It’s a specialized case of the traveling salesman problem where cost can be optimized by considering the triangle inequality. The theorem states that the sum of the length of two sides of a triangle is more than the third side. This fact can be supported by the idea of a straight line being the shortest path between two points. By exploiting the triangle inequality, the metric TSP narrows down the potential solutions, as it eliminates certain combinations of paths that would violate this geometric principle.


Written By:
Mehvish Poshni
Join 2.5 million developers at
Explore the catalog

Free Resources