I've been self-studying the book Algorithms by Papadimitriou, Dasgupta and Vazirani. I am having a hard time with a question about local search involving the traveling salesman problem (TSP).

We'll say a local search algorithm is exact if it always returns a globally optimal solution.

Consider a local search algorithm for TSP that uses neighborhoods defined by $k$-change: two tours $T_0$ and $T_1$ are neighbors if one can delete $j \leqslant k$ edges from $T_0$ and add back another $j$ edges to obtain $T_1$. This is known as the $k$-Opt algorithm.

It's easy to see and the book itself discusses how for low values of $k$ (relative to the number $n$ of vertices), $k$-Opt may get stuck on locally optimal solutions that are not globally optimal. In other words, $k$-Opt is not exact for these values of $k$.

The exercise I'm interested in claims that

$k$-Opt with $k = \lceil n/2 \rceil$ is not exact.

I've tried my hand and searched around but couldn't make it.

I found the paper "Some Examples of Difficult Traveling Salesman Problems", available here (and Papadimitriou is one of the authors by the way). It contains a family of examples for which $k$-Opt with $k < (3n/8)$ is not exact, and uses a particular kind of subgraph (which it calls the diamond) to impose a structure on feasible tours.

I've tried to replicate and extend something like this with little success.

  • $\begingroup$ @InuyashaYagami I guess in theory any one counter example suffices (so you can pick $n$). A family would be nice, though, specifically in the sense that it holds for arbitrarily large $n$ (rather than it being true as a quirk of some specific value of $n$). $\endgroup$ Feb 16, 2022 at 14:26

1 Answer 1


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.

enter image description here

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. enter image description here

  • $\begingroup$ I like this a lot! Ingenious. $\endgroup$ Feb 16, 2022 at 23:32
  • $\begingroup$ @Fimpellizzeri Thanks! Hope I have not made any mistake. Also, I would recommend you to create a separate question post for the second question if possible. The community generally does not advice to ask more than two questions in the same post 😅. $\endgroup$ Feb 16, 2022 at 23:39
  • $\begingroup$ You've made a typo in saying we couldn't keep $(A, H)$, you most definitely meant $(A, G)$, but I could follow along the parts that felt less clear. After removing $(C, H)$, $(A, H)$ must be added because blue edges must be kept and it's the only cost-feasible way to keep the tour going from $H$ (each vertex in the tour must have degree $2$). Something similar holds for $(C, B)$ with vertex $C$. Now, since we've established that $(A, H)$ and $(H, G)$ must be on the tour, $(G, A)$ can't be on the tour, for it would form a too-short cycle. (Continued...) $\endgroup$ Feb 16, 2022 at 23:50
  • $\begingroup$ (... continued) Then, $(G, F)$ must be added because it's the only cost-feasible way to keep the tour going from $G$. Something similar holds for the upper part of the graph. But we've already spent all our budget on edge additions, and can only remove one additional edge: either $(A, F)$ or $(B, E)$. Regardless of our choice, this does not lead to a valid tour. $\endgroup$ Feb 16, 2022 at 23:52
  • $\begingroup$ Do you feel like it would be better to edit this question to be only about $(1)$, and open a second question solely about $(2)$? I could certainly do that, I just worry about hogging the front page. $\endgroup$ Feb 16, 2022 at 23:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.