# Discussion about transformation TSP to UniqueTSP

• Date: Mon, 27 Nov 2006 13:07:30 +0100

Hi,

My usenet client is fed up with depth of discussion about Mr. Diaby TSP
conjecture where algorithm converting TSP to UniqueTSP appeared. Idea was
simple - we shift all weights by large number and add some value to each
weight ensuring that there will be only one optimal solution. I then propose
to continue discussion about H&D algorithm here.

I have proposed N^2 bites shift (adding "extra space"), while there was
discussion "can it be less". In mine opinion minimal shift needs N^log(N) -
we have to separate each number in such way that after adding them we can be
sure that we can distinct what was taken to sum. Following example of
implementation in mine opinion has error in step 3 - if we add same value to
all arcs from city i then in overall cost we will be unable to recognize
sequence used - every sum will contain N x 1 in extra space.

Answering some of doubts discussed previously:

- usage of this transformation for heuristics - I don't feel like it changes
something... For large instances we will have only one unique optimal TSP
tour... but difference to some non-optimal tours may be less then
0.000000001% so heuristics will consider them too

- decision version - each NP-complete problem can be transformed to Hamilton
Cycle problem which can be converted to TSP with question "Is there TSP tour
with overall Cost <=N" (in transformation we assign 1 to every arc existing
in HC instance and 100 for every arc added to obtain TSP instance) - this
makes decision version ask for optimal C, but after transformation we loose
this ability. My attempt to solve it via checking one by one N^2 problems is
incorrect - it will preserve correctness of solution, but it does not ensure
uniqueness of optimal assignment

- there was discussion is UP class of problems or problem instances. For
example there are many SAT instances which has single accepting paths, but
there are also instances having many solutions - so is SAT in UP or outside
UP?

- UP?=NP - I think not - even if above problem was solved. I think that UP
would have been then like NP-complete - in NP and every problem from NP
could have been transformed to UP but it does not imply that UP=NP.

Until/unless we will be able to find some use of this algorithm I feel
slight motivation to finish it up in terms of solid proves...

Best regards,

U¿ytkownik "deepakc" <deepakc@xxxxxxxxxxxxxxxx> napisa³ w wiadomo¶ci
news:1164536766.019077.199280@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Dear Everyone,

I was thinking along the lines that Mr/Ms Mathisart told me
earlier...regarding how to optimize the H&D Algorithm.

And now I have found a more optimized version of the H&D
Algorithm,...we need to now go only upto 2^N and not upto 2^(N^2).
Thank you Mathisart (is that ur real name by the way ?)

Of course, both versions of Algorithms are polynomial in space & time,
but still this one is better:

BETTER VERSION OF HOFMAN & DEEPAK (H&D) ALGORITHM
1.) Multiply all the edges of the TSP with the same large constant
C=(2^N) where N is the number of cities
2.) i=0
3.) Now add 2^i to all Edges coming out of City(i)
4.) i=i+1
5.) Loop to Step 3, until i=(N-1)..that means loop until all Cities
have been covered
6.) Exit

All the 8 Theorems that I mentioned in my previous post "280" also
apply for the above Algorithm.

-Deepak

Hay

.