In the text book, Introduction to Algorithm, 3rd Edition.In the chapter, Approximation Algorithms and for the problem Travelling Salesman Problem, the author says: I am wondering how triangle inequality gives rise to this assertion? It seems that this property is not that important, as I searched through the rest of this section, it does not appear.
without triangle inequality, finding good approximate tours for TSP in polynomial time is impossible unless P=NP?
algorithms;complexity theory;traveling salesman;approximation algorithms