Approximation algorithms and the metric TSP

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.

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 $2$-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 $n$ 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 $n$ 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 $n$ 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.

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 $(n-1)!/2$ possibilities. Just to get a sense of how bad this is, if we take $n=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 $n$ 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.

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.

• For a maximization problem, suppose that $M^*$ is the maximum objective value, but our algorithm produces a solution with objective value $M$. Then the ratio $\frac{M^*}{M}$ tells us how good our solution is relative to the best possible solution. For example, if the ratio is $\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 $\rho(n)$ on this ratio, so that for any problem instance of size $n$,

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

  then $\rho(n)$ is said to be the approximation guarantee for the maximization problem where $0 < M \leq M^*$. When $\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^* \leq \rho(n)\cdot M$$

• For convenience, approximation guarantees are defined to be greater than or equal to $1$. Because of this, the definition of an approximation guarantee is slightly different for minimization problems. The ratio under consideration is $M/M^*$ instead of $M^*/M$, where $M^*$ is the minimum objective value. For a minimization problem, $\rho(n)$ is the approximation guarantee, if

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

  where $0 < M^* \leq M$ for any problem instance of size $n$.

  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 \leq \rho(n)\cdot M^*$$

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

In this blog post, we’ll cover a $2$-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 $2$ 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 $2$-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 $M$ and $M^*$ needs to be established for each conceivable input of size $n$, and since $M^*$ 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 $2$-approximation solution for the metric TSP.

A 2-approximation algorithm#

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

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

Since $L$ 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.

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

Notation#

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

• $M$ denotes the cost of the tour $L$ produced by our algorithm.

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

• The cost function is denoted by $c$.

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

Correctness and proof of a 2-approximation#

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

$$M \leq 2 M^*$$

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

An upper bound on the approximate solution#

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

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

When the walk $W$ 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, $W$ consists of the following sequence of vertices (with repeating occurrences highlighted in red):

$$v_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 $T$. Note that the sequence of first visits corresponds exactly to a preorder traversal of the minimum spanning tree $T$. Since the first and the last vertex in a tour are identical, striking off all the repeat visits except for the last vertex of $W$ gets us exactly the tour returned by our algorithm. If we apply this to our example above, we get the following:

$$\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 $W$, we bypass it, which results in lowering the cost of the resulting walk by the triangle inequality.

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

$$M \leq c(W)$$

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

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

A lower bound on the optimum solution#

Let $M^*$ 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 $P$ on $n$ vertices. As the edge costs are nonnegative, the cost $c(P)$ of the resulting path is at most the cost of the tour:

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

Since $P$ contains all vertices of the graph $G$, it is a spanning tree of $G$. From this, we can infer that its cost is at least as much as that of the minimum spanning tree $T$.

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

Therefore,

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

Multiplying both sides by $2$, we get

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

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

$$M \leq 2\ c (T) \leq 2 M^*$$

In other words, we get

$$M \leq 2 M^*$$

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

Some concluding remarks#

We showed a polynomial-time $2$-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/2$. In a paper presented at STOC 2021 (ACM Symposium on Theory of Computing), this approximation guarantee was (slightly) improved further.