Related Problems: TSP Type: Constructive Algorithm Work on: Graph
Description: Insertion heuristics are quite straight forward, and there are many variants to choose from. The basics of insertion heuristics is to start with a tour of a subset of all cities, and then inserting the rest by some heuristic. The initial subtour is often a triangle or the convex hull. One can also start with a single edge as subtour.

Nearest Insertion, O(n^2)
1. Select the shortest edge, and make a subtour of it.
2. Select a city not in the subtour, having the shortest distance to any one of the cities in the subtoor.
3. Find an edge in the subtour such that the cost of inserting the selected city between the edge’s cities will be minimal.
4. Repeat step 2 until no more cities remain.

Convex Hull, O(n^2*log^2(n))
1. Find the convex hull of our set of cities, and make it our initial subtour.
2. For each city not in the subtour, find its cheapest insertion (as in step 3 of Nearest Insertion). Then chose the city with the least cost/increase ratio, and insert it.
3. Repeat step 2 until no more cities remain.