# Converting MST to TSP Path by Branch Elimination
## 2 Heuristic Algorithms for TSP  
We review the common heuristic found in literature. We consider the following algorithms:  
* Nearest neighbor [17; 18]. * Greedy/Prim-TSP [17; 18]. * Kruskal-TSP [8]. * Christofides [3; 4]. * Cross removal [19]. Figure 2: Idea of the MST-to-TSP algorithm. Branching points and the attached links are first detected. At every step, one of these links is removed and the separated trees are merged by connecting two selected leaf nodes. In this example, two steps are needed to reach the solution of the open-loop TSP. _Nearest neighbor_ (NN) is one of the oldest heuristic methods [17]. It starts from random node and then constructs the tour stepwise by always visiting the nearest unvisited node until all nodes have been reached. It can lead to inferior solutions like 25% worse than the optimum in the example in Figure 3. The nearest neighbor strategy is often applied by human problem solvers in real-world environment [6]. A variant of nearest neighbor in [18] always selects the shortest link as long as new unvisited nodes are found. After that, it switches to the greedy strategy (see below) for the remaining unvisited nodes. In [9], the NN-algorithm is repeated \(N\) times starting from every possible node, and then selecting the shortest tour of all \(n\) alternatives. This simple trick would avoid the poor choice shown in Figure 3. In [14], the algorithm is repeated using all possible _links_ as the starting point instead of all possible nodes. This increases the number of choices up to \(n^{\star}\)(\(n\)-1) in case of complete graph. _Greedy_ method [17; 18] always selects the unvisited node having shortest link to the current tour. It is similar to the nearest neighbor except that it allows to add the new node to both ends of the existing path. We call this as _Prim-TSP_ because it constructs the solution just like Prim except it does not allow branches. In case of complete graphs, nodes can also be added in the middle of the tour by adding a detour via the newly added node. A class of _insertion methods_ were studied in [7] showing that the resulting tour is no longer than twice of the optimal tour. _Kruskal-TSP_[8] also constructs spanning tree like Prim-TSP. The difference is that while Prim operates on a single spanning tree, Kruskal operates on a set of trees (spanning forest). It therefore always selects the shortest possible link as long as they merge to different spanning trees. To construct TSP instead of MST, it also restricts the connections only to the end points. However, while Prim-TSP has only two possibilities for the next connection, Kruskal-TSP has potentially much more; two for every spanning tree in the forest. It is therefore expected to make fewer sub-optimal selections, see Figure 4 for an example. The differences between NN, Prim-TSP, and Kruskal-TSP are illustrated in Figure 5.  
Figure 3: Nearest neighbor algorithm easily fails if unlucky with the selection of starting point. Classical Christofides algorithm [3; 4] includes three steps: (1) Create MST, (2) add links and create Euler tour, and (3) remove redundant paths by shortcuts. Links are added by detecting nodes with odd degree and creating new links between them. If there are \(n\) nodes with odd degree (_odd nodes_), then \(n/2\) new links are added. To minimize the total length of the additional links, perfect matching can be solved by _Blossom algorithm_, for instance [20]. Example of Christofides is shown in Figure 6. In [12], a variant of Christofides was proposed by generating alternative spanning tree that has higher cost than MST but fewer odd nodes. According to [21], this reduces the number of odd nodes from 36-39% to 8-12% in case of TSPLIB and VLSI problem instances. Most of the above heuristics apply both to the closed-loop and open-loop cases. [PERSON] and Kruskal are even better suited for the open-loop cases as the last link in the closed loop case is forced and is typically a very long, sub-optimal choice.