# Re: Discussion regarding Mr. Diabys algorithm

*From*: "deepakc" <deepakc@xxxxxxxxxxxxxxxx>*Date*: 10 Nov 2006 04:13:27 -0800

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

.

**Follow-Ups**:**Re: Discussion regarding Mr. Diabys algorithm***From:*Radoslaw Hofman

**References**:**Re: Discussion regarding Mr. Diabys algorithm***From:*deepakc

**Re: Discussion regarding Mr. Diabys algorithm***From:*Radoslaw Hofman

**Re: Discussion regarding Mr. Diabys algorithm***From:*moustapha . diaby

**Re: Discussion regarding Mr. Diabys algorithm***From:*tchow

**Re: Discussion regarding Mr. Diabys algorithm***From:*deepakc

**Re: Discussion regarding Mr. Diabys algorithm***From:*moustapha . diaby

**Re: Discussion regarding Mr. Diabys algorithm***From:*moustapha . diaby

**Re: Discussion regarding Mr. Diabys algorithm***From:*Radoslaw Hofman

**Re: Discussion regarding Mr. Diabys algorithm***From:*Radosław Hofman

**Re: Discussion regarding Mr. Diabys algorithm***From:*A . L .

**Re: Discussion regarding Mr. Diabys algorithm***From:*deepakc

**Re: Discussion regarding Mr. Diabys algorithm***From:*deepakc

- Prev by Date:
**Re: Discussion regarding Mr. Diabys algorithm** - Next by Date:
**Re: Discussion regarding Mr. Diabys algorithm** - Previous by thread:
**Re: Discussion regarding Mr. Diabys algorithm** - Next by thread:
**Re: Discussion regarding Mr. Diabys algorithm** - Index(es):