Spoiler alert: Euler
Edit: Also a variation on the TSP was part of my senior project so I am forever traumatized.
There are simple <=2x and slightly more complicated <=1.5x guaranteed approximate solutions on metric spaces, but on most spaces there aren't even approximate solutions.
http://nbviewer.jupyter.org/url/norvig.com/ipython/TSP.ipynb