# Converting MST to TSP Path by Branch Elimination
## 2 Heuristic Algorithms for TSP
Christofides, on the other hand, was designed strictly for the closed-loop case due to the creation of the Euler tour. It therefore does not necessarily work well for the open-loop case, which can be significantly worse. There are two strategies how to create open-loop solution from a closed-loop solution. A simple approach is to remove the longest link, but this does not guarantee an optimal result; see Figure 7. Another strategy is to create additional _pseudo node_, which has equal (large) distance to all other nodes [9]. Any closed-loop algorithm can then be applied, and the optimization will be performed merely based on the other links except those two that will be connecting to the pseudo node which are all equal. These two will be the start and end nodes of the corresponding open-loop solution. If the algorithm provides optimal solution for the closed-loop problem, it was shown to be optimal also for the corresponding open-loop case [1]. Figure 4: TSP-Kruskal [8] selected optimal choice for the first eight merges but the ninth merge ends up to sub-optimal result. Overall, only one sub-optimal choice is included, and in this case, it could be fixed by simple local search operations like 2-opt or link swap [9]. Figure 5: Differences between the Nearest Neighbor, Greedy, and Kruskal-TSP after the fourth merge. Nearest neighbor continues from the previously added point. Prim-TSP can continue from both ends. Kruskal has several sub-solutions that all can be extended further. However, when heuristic algorithm is applied, the pseudo node strategy does may not always work as expected. First, if the weights to the pseudo node are small (e.g., zeros), then algorithms like MST would links all nodes to the pseudo node, which would make no sense for Christofides. Second, if we choose large weights to the pseudo node, it would be connected to MST last. However, as the weights are all equal, the choice would be arbitrary. As a result, the open loop case will not be optimized any better if we used the pseudo node than just removing the longest link. Ending up with a good open-loop solution by Christofides seems merely a question of luck. Nevertheless, we use the pseudo node  
Figure 6: Christofides operates by adding links so that Euler tour can be achieved. However, the quality of the result depends on the order in which the links are travelled. In this case, it achieves optimal choice for closed loop solution but not for the open loop case. Figure 3.0 Two strategies for applying closed-loop algorithms for the open-loop cases. First strategy (top) simply removes the longest link, but this does not guarantee optimality even if the closed-loop solution is optimal. Second strategy adds pseudo node with equal distance to all other nodes. The consequence is that there are two long links connected to the pseudo node that can be omitted from the closed-loop solution. This does not affect the optimization at all due to the equal weights. The nodes linked to the pseudo node will become the start and end nodes of the open-loop solution. strategy as it is the de facto standard due to it guaranteeing optimality for the optimal algorithm at least. The existing MST-based algorithms take one of the two approaches: (1) Modify the MST solution to obtain TSP solution [3; 4]; (2) modify the existing MST algorithm to design algorithm for TSP [7; 8; 16; 17]. In this paper, we follow the first approach and take the spanning tree as our starting point. Among other heuristics we mention _local search_. It aims at improving an existing solution by simple operators. One obvious approach is _Cross removal_[19], which is based on the fact that optimal tour cannot cross itself. The heuristic simply detects any cross along the path, and if found, eliminates it by re-connecting the links involved as shown in Figure 3.1 It can be shown that the cross removal is a special case of the more general _2-opt_ heuristic [22]. Another well-known operator is _relocation_ that removes a node from the path and reconnects it to another part of the path.