A simple approximation algorithm for the TSP Consider the following extremely simple approximation algorithm for the TSP.

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


Take any three vertices $a,b,c\in V$ and let $H:=(a,b,c,a).$
While there are vertices in V that are not in H:


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.$
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?
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.