# Discussion about transformation TSP to UniqueTSP

*From*: "Radosław Hofman" <radekh@xxxxxxxxx>*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,

Radek Hofman

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

.

**Follow-Ups**:**Re: Discussion about transformation TSP to UniqueTSP***From:*mathisart

**Re: Discussion about transformation TSP to UniqueTSP***From:*tchow

**Re: Discussion about transformation TSP to UniqueTSP***From:*Radosław Hofman

- Prev by Date:
**Re: Question on computational complexity** - Next by Date:
**New thred of discussion about Mr. Diaby's algorithm** - Previous by thread:
**Water surface in hexahedron** - Next by thread:
**Re: Discussion about transformation TSP to UniqueTSP** - Index(es):