4
$\begingroup$

I am interested in the following version of TSP:

Assumption: TSP where the distances are non-negative. We know the algorithm A which computes the optional solution for such instances of TSP.
Task: State an algorithm that uses the algorithm A and computes an optimal solition for instances where negative distances are allowed.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Are you trying to show a polynomial reduction? Or do you just care about computability? If speed doesn't matter, a brute-force search will work. $\endgroup$ – jmite May 31 '13 at 0:13
  • $\begingroup$ I don't want to show polynomial reduction, i just want to know how to transform instance with negative distances allowed into instance with non-negative distances. Is it more clear now? $\endgroup$ – Dominik_svk May 31 '13 at 0:25
  • $\begingroup$ Just change the instance to make smallest weight 0. $\endgroup$ – user742 May 31 '13 at 1:42
  • $\begingroup$ I thought so. I have to find the smallest negative distance and add this value to each distance in graph(each distance >=0). Right? $\endgroup$ – Dominik_svk May 31 '13 at 7:50
4
$\begingroup$

Hint: Every TSP tour has the same number of edges. Use this to modify the weights in the graph in a way which affects all TSP tours in the same way.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Sorry, but i can't get it. What did you mean by this answer? $\endgroup$ – Dominik_svk May 31 '13 at 7:51
  • 2
    $\begingroup$ That's why it's a hint. $\endgroup$ – Yuval Filmus May 31 '13 at 13:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.