3 ms·

Thanks for the answer, I have edited my post and I have basically the same solution. (Only instead of removing the edges I increase their weight to infinity bec

Thanks for the answer, I have edited my post and I have basically the same solution. (Only instead of removing the edges I increase their weight to infinity because I think the TSP problem is defined only on complete graphs) But as I have mentioned in my comment I feel like this solution is flawed.

zmonx 9y ago
You can without loss of generality assume that the weights are integers (if they are rational, you can multiply all weights so that they become integral). Hence, you can use bisection to compute the actual optimum, not involving epsilon at all.