1996 $$O(n)$$ Algorithm for Finding 4-opt Moves

Gutin2007TheTS, 461.

1998 Arora Algorithm

Gutin2007TheTS, 207-221.

1997 Balas's k-bounded Neighbor

Balas (1996) introduced a class of polynomially solvable TSPs with precedence constraints: Given an integer $$k>0$$ and an ordering $$\sigma:=(1,\ldots,n)$$ of $$N$$, find a minimum cost tour, i.e. a permutation $$\pi$$ of $$\sigma$$, satisfying $$\pi(1)=1$$ and $\pi(i)<\pi(j) \text { for all } i, j \in \sigma \text { such that } i+k \leq j$ Problems in this class can be solved by dynamic programming in time linear in $$n$$, though exponential in k:

THEOREM 1 (Balas 1996). Any TSP with condition (1) can be solved in time $$O(k^22^{k-2}n)$$.

For any fixed $$k$$, we say that such a tour $$T^\prime$$ is a k-bounded neighbor of a tour $$T=c_{\pi[1]},c_{\pi[2]}\ldots,c_{\pi[N]}$$ if for no $$i,j$$ with $$i\ge j+k$$ does city $$c_{\pi[j]}$$ occur after $$c_{\pi[i]}$$ in $$T^\prime$$.

1. $$k=0$$, 此时要求对任意$$i\le j$$, 有$$\pi(i)<\pi(j)$$, 不成立.
2. $$k=1$$, 此时要求对任意$$i+1\le j$$, 即$$i<j$$, 有$$\pi(i)<\pi(j)$$, 该邻域内只有一个序列满足要求, 即$$\sigma$$.
3. $$k=2$$, 此时要求对任意$$i+2\le j$$, 即$$i+1<j$$, 有$$\pi(i)<\pi(j)$$, 该邻域内有$$n-1$$个序列满足要求, 即$$(2, 1,3,4\ldots,n)$$, $$(1,3,2,4,5,\ldots,n)$$, ..., $$(1,2,\ldots,n-2,n,n-1)$$. 以$$(1,2,\ldots,n-2,n,n-1)$$为例做一个说明, 对于该序列中的顶点$$n-1$$, 只要该序列中的前$$n-2$$个顶点比它小就满足邻域定义.

2001 HyperOpt

Gutin2007TheTS, 415.

2003 Tour Merging

Gutin2007TheTS, 436-438.