# Converting MST to TSP Path by Branch Elimination
## 4 Experimental Results
### Results  
Table 2 also shows the average results with the O-Mopsi and Dots data. From these we can learn a few things. First, while the greedy variant of MST-to-TSP provides similar results to that of Kruskal-TSP (4.81% and 2.93%), the all-pairs variant is significantly better (1.69% and 0.61%) and the randomized version reaches near-optimal results (0.07% and 0.02%). In other words, it is clearly superior to the existing MST-based heuristics and very close to the more sophisticated local search (0.00% and 0.01%). Second, by comparing the greedy we can see that the more options the algorithm has for the next merge, the better its performance. Nearest neighbor performs worst as it has only one possibility to continue from the previously added node. Prim-TSP always has two choices and performs better. Kruskal-TSP has often more options for the merge and is the best among these. Randomized Kruskal-TSP is already more competitive but still inferior to MST-to-TSP. Third, Christofides reaches average values of 12.77% (O-Mopsi) and 9.10% (Dots), which are clearly the worst among all tested algorithms. Its advantage is that it is the only algorithm that provides guarantee (50%) for the worst case. However, with these datasets this is merely theoretical as most other heuristics never get worse than 50% anyway. \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \multirow{2}{*}{**Dataset**} & \multirow{2}{*}{**Reference**} & \multirow{2}{*}{**Distance**} & \multirow{2}{*}{**Instances**} & \multirow{2}{*}{\(N\)} & \multicolumn{2}{c}{**Branches:**} \\  & & & & & **Average** & **Max** \\ \hline O-Mopsi & [2] & Haversine & 147 & 4-27 & 0 & 1.90 & 5 \\ Dots & [35] & Euclidean & 6449 & 4-31 & 0 & 1.48 & 11 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Datasets used in the experiments. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline \multirow{2}{*}{**Algorithm**} & \multirow{2}{*}{**Reference**} & \multicolumn{2}{c}{**Average**} & \multicolumn{2}{c}{**Worst**} \\ \cline{3-6}  & & \multicolumn{2}{c}{_O-Mopsi_} & \multicolumn{1}{c}{_Dots_} & \multicolumn{1}{c}{_O-Mopsi_} & \multicolumn{1}{c}{_Dots_} \\ \hline Christofides & [3,4] & 12.77\% & 9.10\% & 35.41\% & 39.21\% \\ Nearest neighbor & [17] & 20.00\% & 9.25\% & 66.57\% & 48.06\% \\ Nearest neighbor+ & [9] & 3.47\% & 1.49\% & 21.01\% & 22.80\% \\ Prim-TSP & [17] & 6.57\% & 3.84\% & 32.95\% & 35.23\% \\ Kruskal-TSP & [8] & 4.87\% & 2.66\% & 28.59\% & 28.40\% \\ Kruskal-TSP (100r) & [8] & 0.77\% & 0.26\% & 7.13\% & 13.46\% \\ MST-to-TSP (greedy) & (proposed) & 4.81\% & 2.93\% & 21.98\% & 28.40\% \\ MST-to-TSP (all-pairs) & (proposed) & 1.69\% & 0.61\% & 16.32\% & 15.46\% \\ MST-to-TSP (all-pairs 100r) & (proposed) & 0.07\% & 0.02\% & 1.98\% & 2.42\% \\
2-opt & [22] & 1.72\% & 1.35\% & 15.53\% & 22.86\% \\ Random Mix Local Search & [9] & 0.00\% & 0.01\% & 0.27\% & 2.59\% \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Accuracy comparison of the algorithms (gap) for the two series of datasets. The only advantage of Christofides is that this 50% upper limit is theoretically proven. For practice, MST-to-TSP is clearly better choice. The dependency on the number of nodes is demonstrated in Figure 15. We can see that the gap tends to increase with the problem size. This is as expected but it remains an open question whether the gap value would converge to certain level with this type of 2-dimensional problem instances. Table 3 shows how the link swaps increase the length of the path when converting the spanning tree to TSP path. Out of the 147 O-Mopsi games, 19 (12%) have no branches and the minimum spanning tree is the optimal solution for TSP as such. Most other games have only one (31%) or two (25%) branches, which shows that the task of converting MST to TSP is not too difficult in most cases. Only about 10% of the games require more than two swaps.