Sorry, an error occurred while loading the content.
Browse Groups

• The following paper is a nice summary of opinions about this classical computer science problem: http://www.cs.umd.edu/~gasarch/papers/poll.pdf And as I was
Message 1 of 3 , Jun 3, 2009
View Source
The following paper is a nice summary of opinions about this classical
computer science problem:
http://www.cs.umd.edu/~gasarch/papers/poll.pdf

And as I was reading it, it occurred to me that it is not obvious for me
how to check a solution to the Travelling Salesman Problem.

Suppose you compute the shortest path for a travelling salesman.
How do you actually check this result?

--- Omer

--
MS-Windows is the Pal-Kal of the PC world.
My own blog is at http://www.zak.co.il/tddpirate/

My opinions, as expressed in this E-mail message, are mine alone.
They do not represent the official policy of any organization with which
I may be affiliated in any way.
WARNING TO SPAMMERS: at http://www.zak.co.il/spamwarning.html
• Do you mean how to verify a solution for TSP in polynomial time? If that s the case, you better look at the TSP as a decision problem: A variant of the
Message 1 of 3 , Jun 3, 2009
View Source
Do you mean how to verify a solution for TSP in polynomial time?
If that's the case, you better look at the TSP as a decision problem:
"A variant of the traveling salesman problem, where we want to know if there is a route of some length that goes through all the nodes in a certain network" http://en.wikipedia.org/wiki/NP_(complexity)#Examples
(This variant is equivalent to the search problem - there's a simple reduction from the decision to the search problem)

Now we can talk about verifying a solution to the decision problem:
1. Make sure the route is indeed in the correct length
2. Verify that all the cities are visited (using some linear space)
3. Verify that no city is visited more than once (using some more small space)
There is no need to check if it's the optimal solution - that's the fun part of it...

I leave you with the correctness ;)
This verifier checks the solution in a polynomial time and therefore the problem is in NP.

Hope that helps (and I didn't do any mistake).
Thanks for the article,

On Wed, Jun 3, 2009 at 11:42 PM, Omer Zak <w1@...> wrote:

The following paper is a nice summary of opinions about this classical
computer science problem:
http://www.cs.umd.edu/~gasarch/papers/poll.pdf

And as I was reading it, it occurred to me that it is not obvious for me
how to check a solution to the Travelling Salesman Problem.

Suppose you compute the shortest path for a travelling salesman.
How do you actually check this result?

--- Omer

--
MS-Windows is the Pal-Kal of the PC world.
My own blog is at http://www.zak.co.il/tddpirate/

My opinions, as expressed in this E-mail message, are mine alone.
They do not represent the official policy of any organization with which
I may be affiliated in any way.
WARNING TO SPAMMERS: at http://www.zak.co.il/spamwarning.html

• ... Yes. ... Is the procedure of reduction executable in polynomial time? ... Why? My question is simple. Given a purported solution to the Travelling Salesman
Message 1 of 3 , Jun 3, 2009
View Source
On Thu, 2009-06-04 at 01:05 +0300, Hadar Weiss wrote:
>
>
> Do you mean how to verify a solution for TSP in polynomial time?

Yes.

> If that's the case, you better look at the TSP as a decision problem:
> "A variant of the traveling salesman problem, where we want to know if
> there is a route of some length that goes through all the nodes in a
> certain network"
> http://en.wikipedia.org/wiki/NP_(complexity)#Exampleswww.
> (This variant is equivalent to the search problem - there's a simple
> reduction from the decision to the search problem)

Is the procedure of reduction executable in polynomial time?

> Now we can talk about verifying a solution to the decision problem:
> 1. Make sure the route is indeed in the correct length
> 2. Verify that all the cities are visited (using some linear space)
> 3. Verify that no city is visited more than once (using some more
> small space)
> There is no need to check if it's the optimal solution - that's the
> fun part of it...

Why?
My question is simple.
Given a purported solution to the Travelling Salesman Problem, how do we
verify that it is the correct solution?
Besides checking that all the cities were visited, how do I verify that
there is no other arrangement of cities which shortens the path
travelled by the salesman? Is it possible at polynomial time at all?

> I leave you with the correctness ;)
> This verifier checks the solution in a polynomial time and therefore
> the problem is in NP.

How about the original Travelling Salesman Problem?

--- Omer
--
One does not make peace with enemies. One makes peace with former
enemies.
My own blog is at http://www.zak.co.il/tddpirate/

My opinions, as expressed in this E-mail message, are mine alone.
They do not represent the official policy of any organization with which
I may be affiliated in any way.
WARNING TO SPAMMERS: at http://www.zak.co.il/spamwarning.html
Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.