[algogeeks] Re: Travelling Salesman Relaxation

Thu, 13 Jul 2006 07:42:49 -0700

As far as I know, TSP has a PTAS, which is based on DP. This result was made by Arora http://ocw.mit.edu/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-854JFall2001/334C4A2D-D89F-460F-9D02-017657FF0759/0/arora.pdf

On 7/13/06, Ioannis Atsonios <[EMAIL PROTECTED]> wrote:

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 [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---

Reply via email to