# Finding the Best 3-OPT Move in Subcubic Time
## 2 Selections, Schemes and Moves  
Let \(G=(V,E)\) be a complete graph on \(n\) nodes, and \(c:E\mapsto\mathbb{R}^{+}\) be a cost function for the edges. Without loss of generality, we assume \(V=\{0,1,\ldots,\bar{n}\}\), where \(\bar{n}=n-1\). In this paper, we will describe an effective strategy for finding either the best improving or any improving move for a given current tour \((v_{1},\ldots,v_{n})\). Without loss of generality, we will always assume that the current tour \(T\) is the tour  
\[(0,1,\ldots,\bar{n}).\]We will be using modular arithmetic frequently. For convenience, for each \(x\in V\) and \(t\in\mathbb{N}\) we define  
\[x\oplus t:=(x+t)\mod n,\qquad\qquad x\ominus t:=(x-t)\mod n.\]  
When moving from \(x\) to \(x\oplus 1,x\oplus 2\) etc. we say that we are moving clockwise, or forward. In going from \(x\) to \(x\ominus 1,x\ominus 2,\ldots\) we say that we are moving counter-clockwise, or backward.  
We define the forward distance \(d^{+}(x,y)\) from node \(x\) to node \(y\) as the \(t\in\{0,\ldots,n-1\}\) such that \(x\oplus t=y\). Similarly, we define the _backward distance_\(d^{-}(x,y)\) from \(x\) to \(y\) as the \(t\in\{0,\ldots,n-1\}\) such that \(x\ominus t=y\). Finally, the distance between any two nodes \(x\) and \(y\) is defined by  
\[d(x,y):=\min\{d^{+}(x,y),d^{-}(x,y)\}.\]  
A 3-OPT move is fully specified by two sets, i.e., the set of removed and of inserted edges. We call a removal set any set of three tour edges, i.e., three edges of type \(\{i,i\oplus 1\}\). A removal set is identified by a triple \(S=(i_{1},i_{2},i_{3})\) with \(0\leq i_{1}<i_{2}<i_{3}\leq n\), where the edges removed are \(R(S):=\{\{i_{j},i_{j}\oplus 1\}:j=1,2,3\}\). We call any such triple \(S\) a selection. A selection is complete if \(d(i_{j},i_{h})\geq 2\) for each \(j\
eq h\), otherwise we say that \(S\) is a partial selection. We denote the set of all complete selections by \(\mathcal{S}\).  
Complete selections should be treated differently than partial selections, since it is clear that the number of choices to make to determine a partial selection is lower than 3. For instance, the number of selections in which \(i_{2}=i_{1}\oplus 1\) is not cubic but quadratic, since it is enough to pick \(i_{1}\) and \(i_{3}\) in all possible ways such that \(d(i_{1},i_{3})\geq 2\) and then set \(i_{2}=i_{1}\oplus 1\). We will address the computation of the number of complete selections for a given \(K\) in Section 2.2. Clearly, if we do not impose any special requirements on the selection then there are \({n\choose 3}=\Theta(n^{3})\) selections.  
Let \(S\) be a selection and \(I\subset E\) with \(|I|=3\). If \((T\setminus R(S))\cup I\) is still a tour then \(I\) is called a _reinsertion set_. Given a selection \(S\), a reinsertion set \(I\) is pure if \(I\cap R(S)=\emptyset\), and degenerate otherwise. Finding the best 3-OPT move when the reinsertions are constrained to be degenerate is \(O(n^{2})\) (in fact, 3-OPT degenerates to 2-OPT in this case). Therefore, the most computationally expensive task is to determine the best move when the selection is complete and the reinsertion is pure. We refer to these kind of moves as true 3-OPT. Thus, in the remainder of the paper, we will focus on true 3-OPT moves.