Re: Discussion regarding Mr. Diabys algorithm

Dear All,

I believe this could be a possible clue for a proof for QUESTION-1. The
answer is yes, Diaby's Algorithm is capable of pinpointing all (N!)
tours. This is a very meta-level proof, but it needs to be converted
into a more mathematical proof.

The meta-level proof is in the following 4 points (and pls correct me
if I am wrong):

1. If you carefully think, you find out that the formulation of the
Assignment Polytope, from the TSP Polytope, can occur in an exponential
number of ways.

2. Lets denote the one and only one TSP polytope as P(TSP), and the
possible Assignment Polytopes as P(APi), where i varies from 1 to N!.
So we have P(TSP)=>P(AP1), P(TSP)=>P(AP2), P(TSP)=>P(AP3),
.......P(TSP)=>P(APN!).

3. For each different Assignment Polytope, we are capable of obtaining
a BFS (Basic Feasible Solution). So P(APi)=>BFSi, where i varies from 1
to N!.

4. Even if a single optimal TSP tour can be obtained from one BFS, it
follows that an exponential number of optimal TSP tours can be obtained
from N! BFS. In other words, BFSi=>Tour(i), where i varies from 1 to N!

Hence proved.

As regards QUESTION-2, I really have no clue as to where to start. And
I believe that QUESTION-2 is the hardest part.

Let me know what you think.
-Deepak

.