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.