Question

Let us call a local search algorithm exact when it always produces the optimum solution. For example, the local search algorithm for the minimum spanning tree problem introduced in Problem 9.5 is exact. For another example, simplex can be considered an exact local search algorithm for linear programming.

(a) Show that the2- change local search algorithm for the TSP is not exact.

(b) Repeat for the $\mathbf{\left[}\frac{\mathbf{n}}{\mathbf{2}}\mathbf{\right]}$- change local search algorithm, where is the number of cities.

(c) Show that $\mathbf{(}\mathbf{n}\mathbf{-}\mathbf{1}\mathbf{)}$-change local search algorithm is exact.

(d) If A is a optimization problem, define A-IMPROVEMENT to be the following search problem: Given an instancexof A and a solutionsof A, find another solution ofxwith better cost ( or report that none exists, and thus is optimum). For example, in TSP IMPROVEMENT we are given a distance matrix and a tour, and we are asked to find a better tour. It turns out that TSP IMPROVEMENT is NP-complete, and so is SET COVER IMPROVEMENT. (Can you prove this?).

(e) We say that a local search algorithm has polynomial iterationif each execution of the loop requires polynomial time. For example, the obvious implementation of the $\mathbf{(}\mathbf{n}\mathbf{-}\mathbf{1}\mathbf{)}$ -change local search algorithm for the TSP defined above does not have polynomial iteration. Show that, unless , there is no exact local search algorithm with polynomial iteration for the TSP and SET COVER problems.

Short answer

(a) The 2-change local algorithm for TSP is not exact.

(b) $\left[\frac{n}{2}\right]$-change local search algorithm is not exact.

(c) $(n-1)$-change local search algorithm is exact.

(d) TSP IMPROVEMENT is NP-complete and SET COVER IMPROVEMENT is also NP-complete.

(e)Unless p = NP , there is no exact local search algorithm with polynomial iteration for the TSP and SET COVER problems.

Step-by-step solution

Local Search Algorithm

The local search algorithm provides the small solution from the neighborhood edges and compares the cost of both the solutions. The local search algorithm is optimal as it replaces the previous search. If the suggested solution costs lesser than the previous one, it replaces the previous solution. The local search algorithm is optimal and is applied in the TSP. The neighborhood structure is imposed on the problem and this is the central part of the local search.

Show that TSP is not exact.

(a)

The given problem considers the local search algorithm is exact. An algorithm is exact when it always produces an optimal solution. The 2-change local search algorithm for the TSP considers the differences in two edges. be the set of tours that is obtained by removing the two edges of and the putting other two edges in.

Since each iteration runs certainly fast, the precise count of iterations that is needed is not found. At this point, it is concluded that the local search is optimal by considering the immediate neighborhood edges. But there are also chances to have better solutions that locate further.

This proves that the 2-change local search algorithm for the TSP is not exact.

The [n2] - change local search algorithm, where is the number of cities is not exact.

(b)

The solution from (a) is considered here with the $\left(\frac{n}{2}\right)$-change local search algorithm, represents the number of cities. In this case, the vertices are divided into two and then replacing them with the new set of vertices from the set of tours. In this case, also, the decisions are made with the immediate neighborhood. Cutting the vertices is not feasible and optimal.

This proves that $\left(\frac{n}{2}\right)$-change local search algorithm is not exact.

Show that (n-1) -change local search algorithm is exact

(c)

To prove $\left(n-1\right)$-change local search algorithm is exact, consider as the number of cities. The change$\left(n-1\right)$ reduces the change to one. In this case, the current vertex is removed and it is replaced by the immediate neighbor that has the lesser cost. This provides the optimal solution.

This proves that $\left(n-1\right)$-change local search algorithm is exact

Prove that SET COVER IMPROVEMENT is NP-complete.

(d)

Given that is an optimization problem. is defined as follows:

is the instance of ,s is the solution of

Let s’ be the other solution with

Compare s and s’

The s’ has the better cost

Or

None of the solutions exists

Thus, s is the optimal solution

Now consider the TSP, Let the TSP-IMPROVEMENT be as follows:

Let d be the distance matrix and t be the tour

Let t' be another tour found with d

Compare t and t'

Compute the better solution from a comparison

if t' is the better tour

then

The solution is t'

else

t is considered as a solution or proceed to compare.

In the above, TSP-IMPROVEMENT, the t' tour finding is non-deterministic and there is a chance of getting a better tour further away.

So, this concludes that TSP-IMPROVEMENT is NP-complete.

Likewise, SET COVERIMPROVEMENT , identifying the subsets is non-deterministic which results that it is also NP-complete.

Show that, unless P=NP, there is no exact local search algorithm with polynomial iteration for the TSP and SET COVER problems.

(e)

Consider the TSP and SET COVER problems discussed in the previous subpart solution. When the local search algorithm is applied on and it is said to be in NP-complete. In this case, exact local search algorithm with polynomial iteration is obtained only if P=NP.

Hence, P=NP proves that there are non-deterministic results that infer the lesser optimal solutions.