# Converting MST to TSP Path by Branch Elimination
## 1 Introduction
The resulting sub-trees are then reconnected by selecting the shortest link between leaf nodes. The second strategy, _all-pairs_, considers all possible removal and reconnection possibilities and selects the best pair. We test the algorithm with two datasets consisting of open loop problem instances with known ground truth: O-Mopsi [2] and Dots [9]. Experiments show that the all-pairs variant provide average gaps of 1.69% (O-Mopsi) and 0.61% (Dots). These are clearly better than those of the existing MST-based variants including Christofides (12.77% and 9.10%), Prim-TSP (6.57% and 3.84%), and Kruskal-TSP (4.87% and 2.66%). Although sub-optimal, the algorithm is useful to provide reasonable estimate for the TSP solution. It is also not restricted to complete graphs with triangular inequality like Christofides. In addition, we also test repeated randomized variant of the algorithm. It reaches results very close to the optimum; averages of 0.07% (O-Mopsi) and 0.02% (Dots). Figure 1: Minimum spanning tree (MST) (left) and open loop travelling salesman problem (TSP) solutions (right) for the same problem instance. The branching nodes are shown by blue, and the links that are different in the two solutions have thicker black line. In addition to the branches, there are only two other places (red circles) where the two solutions differ. Among all links, 29/37 = 78% are the same in both solutions. One of the main motivations for developing heuristics algorithms earlier has been to have a polynomial time approximation algorithm for TSP. Approximation algorithms guarantee that the gap between the heuristic and optimal results has a proven upper limit but these limits are usually rather high: 67% [10], 62% [11], 50% [4], 50%-\(\varepsilon\)[12], and 40% [13]. The variant in [14] was speculated to have limit as low as 25% based on empirical observations. The results generalize to the open-loop case so that if there exists \(\alpha\)-approximation for the closed-loop TSP there exists \(\alpha\)+\(\varepsilon\) approximation for the open-loop TSP [15; 16]. However, for practical purpose, all of these are high. Gaps between 40% to 67% are likely to be considered insufficient for industrial applications. The second motivation for developing heuristic algorithms is to provide initial solution for more complex algorithms. For example, the efficiency of local search and other metaheuristics highly depends on the initial solution. Starting from a poor-quality solution can lead to much longer iterations, or even prevent reaching a high-quality solution with some methods. Optimal algorithms like branch-and-cut also strongly depend on the quality of initialization. The better the starting point, the more can be cut out by branch-and-cut. One undocumented rule of thumb is that the initial solution should be as good as ~1% gap in order to achieve significant savings compared to exhaustive search. The rest of the paper is organized as follows. Section 2 reviews the existing algorithms focusing on the those based on minimum spanning tree. The new MST-to-TSP algorithm is then introduced in Section 3. Experimental results are reported in Section 4 and conclusions drawn in Section 5.