Hello,
Can anybody suggest (and describe) a simple relaxation to the
travelling salesman problem?
I'm only interested in solving small instances and intend to use a
branch-and-bound algorithm.
Regards,
--markus
--~--~-~--~~~---~--~~
You received this message
You can find an answer to your problem in the book Combinatorial
Optimization:Algorithms Complexity,by Steiglitz and Papadimitriou.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to
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
As far as I know, TSP has a PTAS, which is based on DP. This resultwas 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
Thanks to everyone who responded. Your help is highly appreciated!
Gary
--~--~-~--~~~---~--~~
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
input is 3 words abbaaba, ababbad, acabbaad
find max common subword
abba is max word in above example
ur Friend
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send
Look at the prime number 3137. If one digit at a time is deleted, we
generate the sub-numbers 137, 337, 317, 313. All four new of the
sub-numbers are also prime,or sub-primes.
Are there any more 4-digit primes which behave in exactly the same way?
An array of size N has distinct values 1...N in random order. You have
only operator called rev(X) (where X is any value from 0 to N-1) which
reverses all values from 0 to X (example values 2,3,1,4 and rev(2) gets
you 1,3,2,4). Our objective is to sort the array using minimum number
of Rev(X)
