For the set of real numbers R, positive integer n, and the Euclidean norm on R^n, there is the old R. Karp paper where he shows amazing results for: Find a mini

For the set of real numbers R, positive integer n, and the Euclidean norm on R^n, there is the old R. Karp paper where he shows amazing results for: Find a minimum spanning tree and do a depth-first traversal but deleting arcs that have already been traversed and going directly to the city not yet visited that the depth first traversal would visit next. So, just code up one of the at least two famous polynomial and amazingly fast algorithms for minimum spanning tree then write the traversal code. For the Euclidean case, likely tough to beat, all things considered, in practice. Why not stop there? (1) In some cases want to be quite close to optimality or have actual optimality. (2) In some cases, the Euclidean norm need not hold even roughly, e.g., job shop scheduling with setup times.