> Which kind of metric is it used to compare these algorithms? Usually (in particular if the edge weights in the graph are non-negative or even positive) the r

> Which kind of metric is it used to compare these algorithms? Usually (in particular if the edge weights in the graph are non-negative or even positive) the ratio (or sometimes, but more rarely, also the difference) between your attained solution and the optimal solution. > How good are heuristics methods compared to exact solvers? First: For mathematically minded people "heuristics" (in the sense of the video) are to be considered worthless since you rarely can prove anything about the solution attained by it. Even if by definition some result about the solution can be shown (say, that it is optimal in some k-neighbourhood of solutions) this will hardly tell you anything about how good you really are. But one very good heuristic algorithm for which you actually prove something (and thus is really helpful) is the Christophides algorithm (https://en.wikipedia.org/wiki/Christofides_algorithm https://en.wikipedia.org/wiki/Christofides_algorithm), for which one can show that if the edge weights form a metric in the graph you will get a solution that is at most 3/2 as long as the optimal solution.