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