It's an approximate solution with bounded unoptimality, I don't remember the exact bound off the top of my head. Edit: it's 3/2 for Christofides' algorithm. Na

It's an approximate solution with bounded unoptimality, I don't remember the exact bound off the top of my head. Edit: it's 3/2 for Christofides' algorithm. Native dynamic is bad speed but gives accurate solution. It's no good for more than 24 nodes or so. Usually it is good enough, other similar and better attempts try to tighten that bound with more admissible heuristics. E.g. for metric spaces solution is possible to tighten a lot. (Like shortest travel without weights.)