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 nonoptimal tours may be less then
0.000000001% so heuristics will consider them too
 decision version  each NPcomplete 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 NPcomplete  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=(N1)..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
.
 FollowUps:
 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
 Re: Discussion about transformation TSP to UniqueTSP
 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):
Relevant Pages
