Repetitive Nearest-Neighbor Algorithm

Question

suppose that in solving a tsp you use the cheapest link algorithm and find a cheapest link tour with a length of 21400 miles. suppose that you later find out that the length of an optimal tour is 20100 miles. what was the relative error of your cheapest link. tour? express your answer as a percentage, rounded to the nearest tenth of a cent.

Answer 1

Relative error:

(V_wrong-V_right) / (V_right)

Use the given numbers.

(21400-20100) / 20100 = 0.06468...

Or 6.5%