Return to Answer

Answer to the first question:

Please see the following figure for $n = 8$. All the red and black edges have weight $1$. The green edge $(C,H)$ has weight $2$. And, the blue edges have weight $0$. The edges that are not there have weight $\infty$; I have not drawn these edges for simplicity.

Now, note that the cycle $(A,B,C,D,E,F,G,H)$ is the optimal tour with weight $5$. Also, the tour formed by the colored edges (red, green, and blue) has weight $6$. Note that the tour formed by these colored edges is locally optimal to $\lceil n/2 \rceil$ change but it is not globally optimal.

Why colored tour is locally optimal?

Proof: For the sake of contradiction assume that it is not locally optimal. It means that there exist at most four edges in the tour that can be replaced to obtain a smaller weight tour. Observe that to obtain a smaller weight tour, the edge $(C,H)$ must be replaced and the blue edges can not to be replaced. If we replace edge $(C,H)$, then we must add the edges $(C,B)$ and $(A,H)$; otherwise, the weight of the tour will become $\infty$.

After adding these edges, we can not keep edges $(B,D)$ and $(A,H)$ in the tour. Therefore, we must add edges $(D,E)$ and $(G,F)$; otherwise, the weight of the tour will become $\infty$. Now, we must remove edges $(B,E)$ and $(A,F)$.

To complete the tour, we need to add edge $(A,B)$; however, we can not add any more edges since we have already added $4 = n/2$ new edges. Therefore, a tour can only be formed by adding edges $(B,F)$ and $(E,A)$. It makes the weight of the tour $\infty$.

This proves that the tour formed by colored edges is locally optimal.

The technique can be easily generalized to the general value of $n$. For example, see the following figure for $n = 14$. Here, again, the tour formed by the colored edges is locally optimal to $\lceil n/2 \rceil$ change but it is not globally optimal.

Answer to the first question:

Please see the following figure for $n = 8$. All the red and black edges have weight $1$. The green edge $(C,H)$ has weight $2$. And, the blue edges have weight $0$. The edges that are not there have weight $\infty$; I have not drawn these edges for simplicity.

Now, note that the cycle $(A,B,C,D,E,F,G,H)$ is the optimal tour with weight $5$. Also, the tour formed by the colored edges (red, green, and blue) has weight $6$. Note that the tour formed by these colored edges is locally optimal to $\lceil n/2 \rceil$ change but it is not globally optimal.

Why colored tour is locally optimal?

Proof: For the sake of contradiction assume that it is not locally optimal. It means that there exist at most four edges in the tour that can be replaced to obtain a smaller weight tour. Observe that to obtain a smaller weight tour, the edge $(C,H)$ must be replaced and the blue edges can not to be replaced. If we replace edge $(C,H)$, then we must add the edges $(C,B)$ and $(A,H)$; otherwise, the weight of the tour will become $\infty$.

After adding these edges, we can not keep edges $(B,D)$ and $(A,G)$ in the tour. Therefore, we must add edges $(D,E)$ and $(G,F)$; otherwise, the weight of the tour will become $\infty$. Now, we must remove edges $(B,E)$ and $(A,F)$.

To complete the tour, we need to add edge $(A,B)$; however, we can not add any more edges since we have already added $4 = n/2$ new edges. Therefore, a tour can only be formed by adding edges $(B,F)$ and $(E,A)$. It makes the weight of the tour $\infty$.

This proves that the tour formed by colored edges is locally optimal.

The technique can be easily generalized to the general value of $n$. For example, see the following figure for $n = 14$. Here, again, the tour formed by the colored edges is locally optimal to $\lceil n/2 \rceil$ change but it is not globally optimal.

Answer to the first question:

Please see the following figure for $n = 8$. All the red and black edges have weight $1$. The green edge $(C,H)$ has weight $2$. And, the blue edges have weight $0$. The edges that are not there have weight $\infty$; I have not drawn these edges for simplicity.

Now, note that the cycle $(A,B,C,D,E,F,G,H)$ is the optimal tour with weight $5$. Also, the tour formed by the colored edges (red, green, and blue) has weight $6$. Note that the tour formed by these colored edges is locally optimal to $\lceil n/2 \rceil$ change but it is not globally optimal.

Why colored tour is locally optimal?

Proof: For the sake of contradiction assume that it is not locally optimal. It means that there exist at most four edges in the tour that can be replaced to obtain a smaller weight tour. Observe that to obtain a smaller weight tour, the edge $(C,H)$ must be replaced and the blue edges can not to be replaced. If we replace edge $(C,H)$, then we must add the edges $(C,B)$ and $(A,H)$; otherwise, the weight of the tour will become $\infty$.

After adding these edges, we can not keep edges $(B,D)$ and $(A,H)$ in the tour. Therefore, we must add edges $(D,E)$ and $(G,F)$; otherwise, the weight of the tour will become $\infty$.

To complete the tour, we need to add edge $(A,B)$; however, we can not add any more edges since we have already added $4 = n/2$ new edges. Therefore, a tour can only be formed by adding edges $(B,F)$ and $(E,A)$. It makes the weight of the tour $\infty$.

This proves that the tour formed by colored edges is locally optimal.

The technique can be easily generalized to the general value of $n$. For example, see the following figure for $n = 14$. Here, again, the tour formed by the colored edges is locally optimal to $\lceil n/2 \rceil$ change but it is not globally optimal.

Answer to the first question:

Please see the following figure for $n = 8$. All the red and black edges have weight $1$. The green edge $(C,H)$ has weight $2$. And, the blue edges have weight $0$. The edges that are not there have weight $\infty$; I have not drawn these edges for simplicity.

Now, note that the cycle $(A,B,C,D,E,F,G,H)$ is the optimal tour with weight $5$. Also, the tour formed by the colored edges (red, green, and blue) has weight $6$. Note that the tour formed by these colored edges is locally optimal to $\lceil n/2 \rceil$ change but it is not globally optimal.

Why colored tour is locally optimal?

Proof: For the sake of contradiction assume that it is not locally optimal. It means that there exist at most four edges in the tour that can be replaced to obtain a smaller weight tour. Observe that to obtain a smaller weight tour, the edge $(C,H)$ must be replaced and the blue edges can not to be replaced. If we replace edge $(C,H)$, then we must add the edges $(C,B)$ and $(A,H)$; otherwise, the weight of the tour will become $\infty$.

After adding these edges, we can not keep edges $(B,D)$ and $(A,H)$ in the tour. Therefore, we must add edges $(D,E)$ and $(G,F)$; otherwise, the weight of the tour will become $\infty$. Now, we must remove edges $(B,E)$ and $(A,F)$.

To complete the tour, we need to add edge $(A,B)$; however, we can not add any more edges since we have already added $4 = n/2$ new edges. Therefore, a tour can only be formed by adding edges $(B,F)$ and $(E,A)$. It makes the weight of the tour $\infty$.

This proves that the tour formed by colored edges is locally optimal.

The technique can be easily generalized to the general value of $n$. For example, see the following figure for $n = 14$. Here, again, the tour formed by the colored edges is locally optimal to $\lceil n/2 \rceil$ change but it is not globally optimal.

Answer to the first question:

Please see the following figure for $n = 8$. All the red and black edges have weight $1$. The green edge $(C,H)$ has weight $2$. And, the blue edges have weight $0$. The edges that are not there have weight $\infty$; I have not drawn these edges for simplicity.

Now, note that the cycle $(A,B,C,D,E,F,G,H)$ is the optimal tour with weight $5$. Also, the tour formed by the colored edges (red, green, and blue) has weight $6$. Note that the tour formed by these colored edges is locally optimal to $\lceil n/2 \rceil$ change but it is not globally optimal.

Why colored tour is locally optimal?

Proof: For the sake of contradiction assume that it is not locally optimal. It means that there exist at most four edges in the tour that can be replaced to obtain a smaller weight tour. Observe that to obtain a smaller weight tour, the edge $(C,H)$ must be replaced and the blue edges can not to be replaced. If you replace edge $(C,H)$, then you must add the edges $(C,B)$ and $(A,H)$; otherwise, the weight of the tour will become $\infty$. Now, there are two cases:

1. Add edges $(A,B)$. To complete the tour, you then must add the edges $(E,D)$ and $(F,G)$; otherwise, the weight of the tour will become $\infty$. But then, the number of edges added would be $5 > n/2$. Therefore, this set of operations is not allowed.

2. If you do not add edge $(A,B)$. Then, you must add edges $(B,E)$ and $(A,F)$. But then, to complete the tour, you must include edge $(D,G)$ of weight $\infty$. In that case, the cost of the tour will become $\infty$.

This proves that the tour formed by colored edges is locally optimal.

Answer to the first question:

Please see the following figure for $n = 8$. All the red and black edges have weight $1$. The green edge $(C,H)$ has weight $2$. And, the blue edges have weight $0$. The edges that are not there have weight $\infty$; I have not drawn these edges for simplicity.

Now, note that the cycle $(A,B,C,D,E,F,G,H)$ is the optimal tour with weight $5$. Also, the tour formed by the colored edges (red, green, and blue) has weight $6$. Note that the tour formed by these colored edges is locally optimal to $\lceil n/2 \rceil$ change but it is not globally optimal.

Why colored tour is locally optimal?

Proof: For the sake of contradiction assume that it is not locally optimal. It means that there exist at most four edges in the tour that can be replaced to obtain a smaller weight tour. Observe that to obtain a smaller weight tour, the edge $(C,H)$ must be replaced and the blue edges can not to be replaced. If we replace edge $(C,H)$, then we must add the edges $(C,B)$ and $(A,H)$; otherwise, the weight of the tour will become $\infty$.

After adding these edges, we can not keep edges $(B,D)$ and $(A,H)$ in the tour. Therefore, we must add edges $(D,E)$ and $(G,F)$; otherwise, the weight of the tour will become $\infty$.

To complete the tour, we need to add edge $(A,B)$; however, we can not add any more edges since we have already added $4 = n/2$ new edges. Therefore, a tour can only be formed by adding edges $(B,F)$ and $(E,A)$. It makes the weight of the tour $\infty$.

This proves that the tour formed by colored edges is locally optimal.

The technique can be easily generalized to the general value of $n$. For example, see the following figure for $n = 14$. Here, again, the tour formed by the colored edges is locally optimal to $\lceil n/2 \rceil$ change but it is not globally optimal.