World's most popular travel blog for travel bloggers.

[Solved]: Traveling salesman problem - negative distances allowed

, , No Comments
Problem Detail: 

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.

Asked By : Dominik_svk

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12387

0 comments:

Post a Comment

Let us know your responses and feedback