Related Problems: TSP Type: Constructive Algorithm Work on: Graph Complexity:O(n2log2(n))
Description: The Greedy heuristic gradually constructs a tour by repeatedly selecting the shortest edge and adding it to the tour as long as it doesn’t create a cycle with less than N edges, or increases the degree of any node to more than 2.
We must not add the same edge twice of course.

Pseudo code:
1. Sort all edges.
2. Select the shortest edge and add it to our tour if it doesn’t violate any of the above constraints.
3. Do we have N edges in our tour? If no, repeat step 2.

The Greedy algorithm normally keeps within 15-20% of the Held-Karp lower bound.