one type of relaxation is based on triangle inequality.e.g w(x1,x2)+w(x2,x3)<w(x1,x3),where x1,x2,x3 are nodes(often called as euclidean tsp),Christofides gave an algorithm with approximation ratio 1.5. Also there are a lot of variants,you must have in mind that tsp is np-complete ,even if the weights of node is 1,2,3(integers)prooved by Yannakakis,Papadimitriou.
--~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
