A simple approximation algorithm for the TSP

Question

Consider the following extremely simple approximation algorithm for the TSP.

Input: A complete weighted graph $G=(V,E).$

1. Take any three vertices $a,b,c\in V$ and let $H:=(a,b,c,a).$

2. While there are vertices in V that are not in H:

   1. Take one of them, say $v.$ Let $H=(v_1,v_2,...,v_k,v_1),$ where $k$ is the number of distinct vertices currently contained in $H.$
   2. Take as new $H$ the shortest of all the Hamiltonian cycles $(v,v_1,v_2,\ldots,v_k,v),$ $(v_1,v,v_2,\ldots,v_k,v_1),$ $(v_1,v_2,v,\ldots,v_k,v_1),$ $\dots,$ $(v_1,v_2,\ldots,v,v_k,v_1),$ i.e., insert $v$ before every vertex in $H$ and find the shortest Hamiltonian cycle among all those.

Output: $H.$

Obviously, this algorithm has runtime $O(n^2).$

Can anyone give me a lower (or upper) bound on the approximation ratio of this algorithm? Or a worst-case example, for that matter?

Answer 1

General TSP is not approximable within any factor, so your algorithm doesn't really have a chance of working well. A worst-case example: We select one Hamiltonian cycle in the clique and give all its edges weight 1 (assume this cycle is $(v_1, v_2, ..., v_n, v_1)$. All the other edges have some big weight $\alpha(n)$. Now let's have your algorithm start with odd vertices. Between any odd vertices there are only edges with weight $\alpha(n)$ and we don't have any tie breaking rule, so the cycle on odd vertices your algorithm constructs can be totally arbitrary (we can for egample forbid it to contain any edges of the form $(v_i, v_{i+2})$. When the algorithm starts working on the even vertices, it will have just two possible places to put $v_i$: after $v_{i-1}$ or before $v_{i+1}$. Again we have no tie-breaking rule, so we can assume that it always choses to put $v_i$ after $v_{i-1}$ (of course we do all this modulo $n$). When we look at the constructed cycle, we see that it is built of alternating weight 1 and weight $\alpha(n)$ edges. So we have $OPT = n$, and our solution has weight ${n \over 2} + {\alpha(n) \over 2}$. We can chose $\alpha$ arbitrarily to disprove any claimed approximation factor. There are some technicalities involved with encoding weight $\alpha$; when we increase $\alpha$ the input size also grows (but more slowly), but still I think we can get any factor.

Answer 2

This is called an insertion heuristic. The general TSP cannot be approximated unless $P=NP$. The question is more interesting for the metric TSP. In that case, Rosenkrantz et al. (1974) show that your heuristic gives an $O(\log n)$ approximation.

You can also try to choose a good vertex $v$ to be inserted in each step, instead of just taking an arbitrary one. One variant is farthest insertion in which $v$ is chosen such that is has maximum distance from the current $H$. Another variant is nearest insertion in which $v$ is chosen such that it has minimum distance from the current $H$. Yet another possibility is cheapest insertion in which $v$ is chosen such that the new $H$ has minimum length. Rosenkrantz et al. show that both nearest and cheapest insertion give a $2-2/n$ approximation and this is tight.

The full reference is: D. Rosenkrantz, R. Stearns, and P. Lewis II. An analysis of several heuristics for the traveling salesman problem. SIAM Journal on Computing, 6(3):563-581, 1977.

Answer 3

As proven here, general TSP is NPO-complete. This means you can either solve it exactly in exponential time or approximate it in polynomial time with an approximation factor growing exponentially with the length of the input. This means that your algorithm, when applied to general TSP instances, cannot give a better guarantee than a factor $O(2^{n^\epsilon})$ for some $\epsilon > 0$.

Different versions of TSP admit different bounds on approximation algorithms. For an overview, the site "A compendium of NP optimization problems" lists a number of TSP variants here. Wikipedia also gives a lot of bounds on its page about TSP, in this section and in this section.