# traveling salesman – Can the “closest neighbor” algorithm get arbitrarily bad in TSP?

Let’s consider the following simple algorithm for attacking the Travelling Salesman Problem:

Choose the pair of cities $$(A,B)$$ where $$Aneq B$$ and the distance between $$A, B$$ is minimal amongst all the distances of the cities. Start with $$A$$, then visit $$B$$, then in each step visit the nearest city not visited already, until there is no more city left.

Given $$kin mathbb{N}$$, is there a setting of cities such that the total distance travelled is more than $$k$$ times the distance travelled in an optimal solution?