Discussion about transformation TSP to UniqueTSP



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


.



Relevant Pages

  • Fast Generators of Incomplete Solutions for Prime Queens
    ... problem are described and implemented in Scheme: queens-prime, ... The queens-prime algorithm ... include the following constraint in our set of constraints: ... For example the following transformation produces a set of ...
    (comp.lang.scheme)
  • Re: JSH: Binary quadratic Diophantines
    ... refers to the transformation of a quadratic equation in two variables ... Step 2 algorithm solves the simpler form. ... that Diophantine equations ARE special in various ways. ... But the world will not know until someone does the math. ...
    (sci.physics)
  • Re: Infinite One-Time Pad, is this product BS?
    ... I will discuss here how Infinite One-Time Pad works according ... This transformation doesn't involve any kind of encryption with a secret ... file to someone you need to also send the "secret file". ... If you have one algorithm, ...
    (sci.crypt)
  • Re: JavaScript code mangler / scrambler / ... khm, more than obfuscator... :)
    ... closer to that than to a transformation at the algorithmic level. ... squaring function), and I pointed that out in my answer. ... It means there is no algorithm that can ... whether ahalts, and if it halts, if execution even reaches the `return' ...
    (comp.lang.javascript)
  • REPOST: Identity as Mathematical and Computer Theory- resolver
    ... A curve as the third order function is to be written, ... So to test the function an algorithm to symbolically ... A transformation of number order to the function's ... or number order detector demonstrated. ...
    (sci.crypt)