Re: Discussion about transformation TSP to UniqueTSP
 From: "deepakc" <deepakc@xxxxxxxxxxxxxxxx>
 Date: 28 Nov 2006 06:30:26 0800
deepakc wrote:
Radoslaw Hofman wrote:
Hi,
Does it make any difference? We can transform every NP problem to HC
and then build TSP with question PATH==N, that means that every NP
problem can be transformed to version having == in question.
In mine opinion <= is used to show that we are asking for optimal tour
instead of tour of size N, but it does not matter for me.
Cheers,
Radek Hofman
Hmmm, yes u're right !!
somehow it escaped me.
Dear Radek,
I had second thoughts, and now I think what you wrote above might be
wrong. The reason is suppose Mr. X gives me an original TSP and asks me
"Does there exist a TSP tour of length = 1000000", where I know for
certain that there cannot be such a tour, because 1000000 is > the sum
of the costs of all TSP Edges. In that case, I can confidently give a
NO answer to Mr. X, within Polynomial time (i.e. time for summing up
all Edge costs).
So the Question is more difficult.....whether or not the YES/NO
Question is NPComplete, actually depends on the value of C.
But one thing is for certain....is that we cannot simply say "Convert
to HCP and then get a Question of whether there is tour of length = N".
That is most probably wrong, because it means that the problem is
difficult, though it is supposed to be easy in certain cases, like what
I showed above.
I am still not sure, but that is what I think.
Deepak
.
 FollowUps:
 Re: Discussion about transformation TSP to UniqueTSP
 From: Radoslaw Hofman
 Re: Discussion about transformation TSP to UniqueTSP
 References:
 Discussion about transformation TSP to UniqueTSP
 From: Radosław Hofman
 Re: Discussion about transformation TSP to UniqueTSP
 From: tchow
 Re: Discussion about transformation TSP to UniqueTSP
 From: deepakc
 Re: Discussion about transformation TSP to UniqueTSP
 From: Radoslaw Hofman
 Re: Discussion about transformation TSP to UniqueTSP
 From: deepakc
 Discussion about transformation TSP to UniqueTSP
 Prev by Date: Re: Discussion regarding Mr. Diabys algorithm
 Next by Date: Re: Discussion about transformation TSP to UniqueTSP
 Previous by thread: Re: Discussion about transformation TSP to UniqueTSP
 Next by thread: Re: Discussion about transformation TSP to UniqueTSP
 Index(es):
Relevant Pages
