2. The 2-opt algorithm for TSP

2-opt swap move

$\text{SWAP-MOVE}(H)$:

1. Given some route $H$, we choose two non-adjacent edges in the cycle.
2. Compare the weight of these two edges. $d(x+y)+d(u,v)$ with $d(x,v)+d(u,y)$
3. If the second pair of edges are smaller than the first, $d(x+y)+d(u,v)>d(x,v)+d(u,y)$, we replace the two first edges to reduce our total graph weight.
4. Ensure the swap does not disconnect the graph.

2-opt approximation algorithm

The 2-opt algorithm is a polynomial-time algorithm for solving TSP that is no worse than twice the global optimal solution.

Given some graph $G$. We can use a Minimum Spanning Tree algorithm to produce tree $T_0$. Then perform Preorder traversal on the nodes in order to find a Hamiltonian cycle $H_0$. Using this path, we perform 2-opt swap move on $H_i$ while the path is not optimal.

$\text{2OPT}(G)$:

1. Construct MST $T_0$ of $G$
2. Let $H_0$ be the preorder traversal of $T_0$.
3. While $H_i$ is not local optimal:
   1. $H_{i+1}\leftarrow \text{SWAP-MOVE}(H_i)$
4. Return $H$

[todo:gif of pdf slides running algorithm]

Proving Approximation Ratio for 2-opt

Theorem: the 2-opt algorithm has an approximation ratio of $R=2$. Proof:

1. Let $H_{\text{approx}}$ and $H_{\text{global}}$ denote the local optimum found by 2-opt and the global optimum Hamiltonian cycle respectively. We want to show $\text{length of}(H_{\text{approx}})\le 2\cdot \text{length of}(H_{\text{global}})$.
2. Remove one edge from $H_{\text{global}}$ to create a path $T$. $\text{length of}(T)\le \text{length of}(H_{\text{global}})$ This new path $T$ is a tree and still connects all points.
3. Let $T_0$ denote the minimum spanning tree as computed by the first step of the 2-opt. It follows that $\text{length of}(T_0)\le \text{length of}(T)$.
4. The length of the preorder traversal $H_0$ is at most twice the length of the spanning tree. $\text{length of}(H_0)\le 2\cdot \text{length of}(T_0)$
5. Every application of the 2-opt swap only goes to further reduce the length of the cycle, such that: $\text{length of}(H_{\text{approx}})\le \dots \le \text{length of}(H_1)\le \text{length of}(H_0)$
6. Hence we can summarise this as: $$\begin{array}{rl}\text{length of}(H_{\text{approx}})& \le \text{length of}(H_0)\\ & \le 2\cdot \text{length of}(T_0)\\ & \le 2\cdot \text{length of}(T)\\ & \le 2\cdot \text{length of}(H_{\text{global}})\text{ as required}\end{array}$$

Hence, we can also state that TSP is 2-approximable.

Some algorithms push this further, such as the Christofides ‘76 algorithm, which is $\frac{3}{2}$-approx.