Path: ...!Xl.tags.giganews.com!local-3.nntp.ord.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Tue, 04 Feb 2025 17:20:02 +0000
Date: Tue, 4 Feb 2025 11:20:02 -0600
MIME-Version: 1.0
User-Agent: Mozilla Thunderbird
Subject: Re: Discussion regarding Mr. Diabys algorithm
Newsgroups: comp.theory
References: <1162631325.660303.157230@h54g2000cwb.googlegroups.com>
Content-Language: en-US
From: olcott <NoOne@NoWhere.com>
In-Reply-To: <1162631325.660303.157230@h54g2000cwb.googlegroups.com>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
X-Antivirus: Norton (VPS 250204-6, 2/4/2025), Outbound message
X-Antivirus-Status: Clean
Message-ID: <apKdnU49Qoff0T_6nZ2dnZfqlJydnZ2d@giganews.com>
Lines: 140
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-pxvneafxMv8VMyILKlNeDnagZB8dvkiUoJ367f8sv1EihNWQ23cdpPYgFep+hH9wscXzWLgzLyzJn48!nNBndaS1NrrrmoLurISbfnu1RFbPBkUyqZYz/58MO9fOFh4kEII9qctoysE05i5e/b8QV31foiA=
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
Bytes: 7185

On 11/4/2006 3:08 AM, Radoslaw Hofman wrote:
> 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 )
> 

I have spoken with Ben since 2006 too.

-- 
Copyright 2024 Olcott

"Talent hits a target no one else can hit;
  Genius hits a target no one else can see."
  Arthur Schopenhauer