Re: Discussion regarding Mr. Diabys algorithm

Hi all,
 Below is discussion I find very interesing, and I think should be
publicated (author of discussion didn't know how to start thread in
USENET). Answer and discussion will be send as reply.
 

>

From: #DEEPAK PONVEL CHERMAKANI# [mailto:deepakc@pmail.ntu.edu.sg]
Sent: Friday, November 03, 2006 9:27 AM
To: radekh@teycom.pl; tchow@alum.mit.edu; tchow@umich.edu;
tchow@lsa.umich.edu; moustapha.diaby@business.uconn.edu
Subject: Regarding Diaby's work on the TSP
Importance: High
 Dear Sir Rodaslaw Hoffman, Sir Tim Chow, and Sir Diaby,
 I am Deepak. I am Chairman of the "Brain Modeling / Intelligent
Systems" Special Interest Group of MENSA Singapore -
www.mensa.org.sg/sig
 I have so far completed my Bachelors Degree at Nanyang Tech Univ,
Singapore, which I completed in 2003. I am currently working as a
Software Engineer.
 I have read Dr. Diaby's work, and have also read the postings at:
http://groups.google.com.nf/group/comp.theory/browse_thread/thread/84ee8d0d661df004/895038fb4f34704a?lnk=raot&hl=en
 I would like to share with all of you, regarding what I think about
Diaby's work. I have basically written what I think is a shortened
version of Diaby's algorithm.
 Please read VERY CAREFULLY ALL SEVEN steps of the Algorithm in the
attachment.
 I hope my attachment is able to answer the below comment made by Sir
Hoffman in the google posting.
  COMMENT made by Sir Hoffman on 27 Oct 2006:
-------------------------
BTW: what background do you have on complexity theory? If you had it,
then you would realize consequences of my last arguments (those with
figures and cardinality of power-set over n!). Imagine problem instance
for n=100. Let us assume that 25% of solutions are optimal. Can your
model "list" them all? No!
 There would be 100!/4=X/4*10^24=[BIG NUMBER]*10^24 optimal solution,
while your model is capable to store no more then 10^18 different
solutions. If then in your model you cannot recognize EVERY possible
solution why are you so sure, that there are no NON-TSP paths combined
together?
-------------------------
  please feel free to give me your opinions via email on what I have
said. Or pls tell me how may I perform a posting in the google website.
So that we may discuss on the google website.
 Best Regards,
-Deepak
 

ATTACHEMENT>>>>>>>>>>>>>>>>>>>>>

 Algorithm of Dr. Diaby -
http://www.business.uconn.edu/users/mdiaby/tsplp/
 1.) Formulate the TSP's constraints as a Linear Program (LP), with
polynomial number of variables.
 2.) Within polynomial time, the LP generates a single SOLUTION. This
SOLUTION represents all the optimal solutions of the TSP. But this
SOLUTION is by itself not a TSP tour .... it is only a result generated
by the LP.
 3.) Within polynomial time, one can systematically generate a single
optimal TSP tour from this LP's SOLUTION (this is true whether the TSP
has polynomial number of optimal tours, or whether the TSP has an
exponential number of optimal tours).
 4.) Within polynomial time, one can systematically generate a
polynomial number of optimal TSP tours from this LP's SOLUTION (this
is true whether the TSP has polynomial number of optimal tours, or
whether the TSP has an exponential number of optimal tours).
 5.) Within exponential time, one can systematically generate an
exponential number of optimal TSP tours from this LP's SOLUTION (this
is true if the TSP has an exponential number of optimal tours).
 6.) But since the definition of the TSP is to find at least one optimal
tour, therefore there is no need to even care about steps 4, and 5,
mentioned above. We only need to care about Step 3.
 7.) It follows from the above 6 steps that therefore, Diaby's
Algorithm is able to find at least one optimal tour to any given TSP,
within polynomial time.
   The major drawback, according to me, with Diaby's paper, is that
there is no necessity for him to draw parallels with "flows" and
"layers". I know that Dr. Diaby's intention may have been to try
explaining the concept better in terms of "flows" and "layers".
But according to me, this explanation in terms of "flows" &
"layers" is only creating confusion, because it is difficult for
one to visualize the fact that the LP SOLUTION represents all the
optimal TSP tours.
By explaining in terms of "flows" and "layers", it is difficult
to imagine that 1,000,000,000 rivers will join together and still be a
resultant-river with the size of only 100 rivers, but where the
resultant-river still represents all the 1,000,000,000 rivers. There is
no way of explaining this concept in terms of multi-commodity flows. In
fact, I cannot imagine is there is any "real-life parallel" of
explaining this concept. So I feel Dr. Diaby should remove this
explanation of "flows" and "layers".
If I were to be Dr. Diaby, I would simply write my paper within 8
pages, explaining all the 7 points mentioned above. Finally, there is
no need to even show experimental result with the 7-city and 8-city
TSP, because that's not needed. This is a proof, and so no
experiments need support this.
  Otherwise, in my opinion, Diaby's algorithm is able to Polynomially
solve the TSP, and the TSP is Polynomially solvable.
 - Deepak Ponvel Chermakani, IEEE Member, 4 Oct 2006
( Chairman of MENSA Singapore's Brain Modeling Group -
www.mensa.org.sg/sig )