We establish the all‑exp property for the Traveling Salesman Problem (TSP) under the $2$‑opt neighborhood and for $(3,2,2)$ and $(2,3,2)$ Maximum Constraint Assignment (MCA) under the flip neighborhood. The all‑exp property means that there exist infinitely many instances with an initial solution such that every improving sequence to a local optimum has exponential length, so any run of local search takes exponential time.
For TSP, all‑exp was already known for every $k$‑opt neighborhood with $k\ge 3$; our result completes the picture by handling $k=2$, thus covering all $k$‑opt cases. In $(p,q,r)$‑MCA, each constraint involves at most $p$ variables, each variable appears in at most $q$ constraints, and each domain has size $r$. We prove all‑exp for the two parameter settings $(3,2,2)$ and $(2,3,2)$, and show that decreasing any of these parameters makes every improving flip sequence polynomially bounded, demonstrating the tightness of our results.
All three findings settle long‑standing open problems. The proofs rely on a common construction technique that reveals a close connection among the local‑search dynamics of these problems.
Review: This work not only fills the theoretical gap for $2$‑opt TSP but also precisely delineates the boundary where MCA exhibits exponential‑time local search, offering valuable insight into the limits of local‑search algorithms.