Re: Discussion regarding Mr. Diabys algorithm




Uzytkownik "deepakc" <deepakc@xxxxxxxxxxxxxxxx> napisal w wiadomosci
news:1163176404.767674.229170@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
king...@xxxxxxxxxxx wrote:

Hmmm...that will be possible, in my opinion. We could try and find a
counter-example, say with 6 cities, or 8 cities or 10 cities or 12
cities. But we have to do a lot of "playing around" with the inter-city
costs, before such a counter-example for Diaby's Algorithm is found.
In fact, I would like to modify my above phrase from "Diaby's Algorithm
is absolutely independent of TSP size" to "the probability of finding a
counter-example increases with TSP size". And the reason is because the
overall number of constraints in Diaby's Model exceeds the number of
possible TSP tours, when N=6,8,10, or 12.

But I will stress that IT IS DEFINITELY POSSIBLE, for us to find a
counter-example for Diaby's Algorithm, when the N=6, 8, 10, etc. This
is because of the ILP to LP relaxation. But as I said, we have to a lot
of playing around with inter-city costs, and some very good computers &
programs could help us do that.

Maybe it is possible to create such combination for small instances - my
goal was to to show that it has lower overall cost... It took me 32
cities... But if Diaby would have be more precise with his model (BLP would
have contained equation 2.13) then it would have been to weak - I would have
used 52 cities (remember that Moews predicted theoretical number of 59 as
"killing" for algorithm).

Best regards,

Radek Hofman


.