Solution Found!
Let us call a local search algorithm exact when it always produces the optimum solution
Chapter 9, Problem 9.10(choose chapter or problem)
Let us call a local search algorithm exact when it always produces the optimum solution. Forexample, the local search algorithm for the minimum spanning tree problem introduced in 9.5 is exact. For another example, simplex can be considered an exact local search algorithmfor linear programming.(a) Show that the 2-change local search algorithm for the TSP is not exact.(b) Repeat for the dn2e-change local search algorithm, where n is the number of cities.(c) Show that the (n 1)-change local search algorithm is exact.(d) If A is an optimization problem, define A-IMPROVEMENT to be the following search problem:Given an instance x of A and a solution s of A, find another solution of x with better cost (orreport that none exists, and thus s is optimum). For example, in TSP IMPROVEMENT we aregiven a distance matrix and a tour, and we are asked to find a better tour. It turns out thatTSP IMPROVEMENT is NP-complete, and so is SET COVER IMPROVEMENT. (Can you provethis?)(e) We say that a local search algorithm has polynomial iteration if each execution of the looprequires polynomial time. For example, the obvious implementations of the (n 1)-changelocal search algorithm for the TSP defined above do not have polynomial iteration. Showthat, unless P = NP, there is no exact local search algorithm with polynomial iteration forthe TSP and SET COVER problems.
Questions & Answers
QUESTION:
Let us call a local search algorithm exact when it always produces the optimum solution. Forexample, the local search algorithm for the minimum spanning tree problem introduced in 9.5 is exact. For another example, simplex can be considered an exact local search algorithmfor linear programming.(a) Show that the 2-change local search algorithm for the TSP is not exact.(b) Repeat for the dn2e-change local search algorithm, where n is the number of cities.(c) Show that the (n 1)-change local search algorithm is exact.(d) If A is an optimization problem, define A-IMPROVEMENT to be the following search problem:Given an instance x of A and a solution s of A, find another solution of x with better cost (orreport that none exists, and thus s is optimum). For example, in TSP IMPROVEMENT we aregiven a distance matrix and a tour, and we are asked to find a better tour. It turns out thatTSP IMPROVEMENT is NP-complete, and so is SET COVER IMPROVEMENT. (Can you provethis?)(e) We say that a local search algorithm has polynomial iteration if each execution of the looprequires polynomial time. For example, the obvious implementations of the (n 1)-changelocal search algorithm for the TSP defined above do not have polynomial iteration. Showthat, unless P = NP, there is no exact local search algorithm with polynomial iteration forthe TSP and SET COVER problems.
ANSWER:Step 1 of 6
The local search algorithm provides the small solution from the neighbourhood edges and compares the cost of both the solutions. If the suggested solution costs lesser than the previous one, it replaces the previous solution. The local search algorithm is optimal applies in the TSP. The neighbourhood structure will be imposed in the problem and this is the central part of the local search.
.