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