Re: Discussion regarding Mr. Diabys algorithm

Uzytkownik "deepakc" <deepakc@xxxxxxxxxxxxxxxx> napisal w wiadomosci
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


Relevant Pages

  • Re: An algorithm questions
    ... Mathieu Dutour -- Doubly linked list in two arrays + a array ... Richard Harter -- The devil's list algorithm ... The storage costs are: ... dependent; I prefer to use unsigned char arrays for that reason; YMMV. ...
  • Re: puzzle
    ... >> Christopher Barber wrote: ... > sometimes misuse) obscure words and to insert long paragraphs of ... given the choice between an algorithm that costs n*n steps ... > than you that would call such an algorithm "close to" O. ...
  • Re: FAQ 5.38 How do I select a random line from a file?
    ... line you've hit (by searching backwards and forwards for $/). ... The algorithm above ensures that the probability of selecting a line is precisely 1/N where N is the total number of lines in the file. ... my %linePostiion; ... but the big question is whether this costs more or less then Knuth's algorithm. ...
  • Re: abstract constructor performance?
    ... >in spending a week optimising a routine that will hardly every be called. ... >used techniques with horrifying costs in space or time, ... algorithm and optimising the implementation of the algorithm. ... Thoought on the selection of an algorithm is a good plan, ...
  • Re: CodeWarrior 10 on Macintel
    ... Remind me, how does this help anybody whose algorithm isn't covered by ... and it costs me less now because Apple is no longer treating ... >typos and/or dropped words render interpretation difficult for me. ...