June 2014
Intermediate to advanced
512 pages
17h 55m
English
Using the notion of polynomial-time Turing reducibility, it is not hard to show that the search problem of TSP that asks for the minimum-cost tour is equivalent to the above decision problem (see Exercise 2.18). Therefore, the search problem of TSP is also NP-hard. In the following, we show that the approximation to TSP is also NP-hard.
For each graph G with a cost function c on its edges, let denote the cost of ...