# Finding the Best 3-OPT Move in Subcubic Time
## 4 Searching the 3-OPT Neighborhood  
As discussed in Section 2.1, the pure 3-OPT reinsertion schemes are four (see Figure 1), namely :  
\[r_{1}=<+3,+2>\hskip 28.452756 ptr_{2}=<-2,-3>\hskip 28.452756 ptr_{3}=<+3,-2> \hskip 28.452756 ptr_{4}=<-3,+2> \tag{1}\]  
Notice that \(r_{3}\) and \(r_{4}\) are symmetric to \(r_{2}\). Therefore, we can just consider \(r_{1}\) and \(r_{2}\) since all we say about \(r_{2}\) can be applied, mutatis mutandis (i.e., with a suitable renaming of the indices), to \(r_{3}\) and \(r_{4}\) as well. Given a move \(\mu=(S,r)\in\mathcal{M}\), where \(S=(i_{1},i_{2},i_{3})\), its value is the difference between the cost of the set \(R(S)=\{\{i_{1},i_{1}\oplus 1\},\{i_{2},i_{2}\oplus 1\},\{i_{3},i_{3}\oplus 1\}\}\) of removed edges and the cost of the reinsertion set \(I(r,S)\). We will denote the value of the move \(\mu\) by  
\[\Delta((i_{1},i_{2},i_{3}),r).\]A key observation is that we can break-up the function \(\Delta()\), that has \(\Theta(n^{3})\) possible arguments, into a sum of functions of two parameters each (each has \(\Theta(n^{2})\) arguments). That is, we will have  
\[\Delta((i_{1},i_{2},i_{3}),r)=f_{r}^{12}(i_{1},i_{2})+f_{r}^{23}(i_{2},i_{3})+f _{r}^{13}(i_{1},i_{3}), \tag{2}\]  
for suitable functions \(f_{r}^{12}(),f_{r}^{23}(),f_{r}^{13}()\), each representing the contribution of a particular pair of indices to the value of the move. The domains of these functions are subsets of \(\{0,\ldots,\bar{n}\}\times\{0,\ldots,\bar{n}\}\) which limit the valid input pairs to values obtained from two specific elements of a selection. For \(a,b\in\{1,2,3\}\), with \(a<b\), let us define  
\[\mathcal{S}_{ab}:=\{(x,y):\exists(v_{1},v_{2},v_{3})\in\mathcal{S}\text{ with }v_{a}=x\text{ and }v_{b}=y\}. \tag{3}\]  
Then the domain of \(f_{r}^{12}\) is \(\mathcal{S}_{12}\), the domain of \(f_{r}^{23}\) is \(\mathcal{S}_{23}\) and the domain of \(f_{r}^{13}\) is \(\mathcal{S}_{13}\). The functions \(f_{r}^{12},f_{r}^{23},f_{r}^{13}\) can be obtained through the functions \(\tau^{+}()\) and \(\tau^{-}()\) as follows:  
\[\{r_{1}\colon\}\text{ We have }I(r_{1})=\{\{i_{1},i_{2}\oplus 1\},\{i_{2 },i_{3}\oplus 1\},\{i_{1}\oplus 1,i_{3}\}\}\text{ (see Figure 1) so that }\Delta((i_{1},i_{2},i_{3}),r_{1})=\] \[=\left[c(i_{1},i_{1}\oplus 1)+c(i_{2},i_{2}\oplus 1)+c(i_{3},i_ {3}\oplus 1)\right]-\left[c(i_{1},i_{2}\oplus 1)+c(i_{2},i_{3}\oplus 1)+c(i_{1} \oplus 1,i_{3})\right]\] \[=\left[c(i_{1},i_{1}\oplus 1)-c(i_{1},i_{2}\oplus 1)\right]+ \left[c(i_{2},i_{2}\oplus 1)-c(i_{2},i_{3}\oplus 1)\right]+\left[c(i_{3},i_{3} \oplus 1)-c(i_{3},i_{1}\oplus 1)\right]\] \[=\tau^{+}(i_{1},i_{2})+\tau^{+}(i_{2},i_{3})+\tau^{+}(i_{3},i_{1 }). \tag{4}\]  
The three functions are  
\[f_{r_{1}}^{12}:(x,y)\in\mathcal{S}_{12}\mapsto\tau^{+}(x,y);\] \[f_{r_{1}}^{23}:(x,y)\in\mathcal{S}_{23}\mapsto\tau^{+}(x,y);\] \[\Delta((i_{1},i_{2},i_{3}),r).\]0 \[\Delta((i_{1},i_{2},i_{3}),r).\]1 \[\Delta((i_{1},i_{2},i_{3}),r).\]2 \[\Delta((i_{1},i_{2},i_{3}),r).\]3  
The three functions are  
\[\Delta((i_{1},i_{2},i_{3}),r).\]4 \[\Delta((i_{1},i_{2},i_{3}),r).\]5 \[\Delta((i_{1},i_{2},i_{3}),r).\]6  
(For convenience, these functions, as well as the functions of some other moves described later on, are also reported in Table 2 of Section 6). The functions \(f_{r}^{12},f_{r}^{23},f_{r}^{13}\) are used in our procedure in two important ways. First, we use them to decide which are the most likely pairs of indices to belong in an optimal selection for \(r\) (the rationale being that, the higher a value \(f_{r}(x,y)\), the more likely it is that \((x,y)\) belongs in a good selection). Secondly, we use them to discard from consideration some moves which cannot be optimal. These are the moves such that no two of the indices give a sufficiently large contribution to the total. Better said, we keep in consideration only moves for which at least one contribution of two indices is large enough.