One criticism of the nearest-neighbor TSP heuristic is that the last edge added (from the last city back to the starting city) can be very long. How much effect can that last edge have on the ratio NN/OPT ?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.