DNA Arrays and the Traveling Salesman Problem

Disappointingly, we found that a 2-opt optimization of the greedy TSP-tour leads to only 0.3% improvement (Table 1). We tried a few approaches to further improve the TSP solution (or to verify its proximity to the optimal solution), in particular, solving minimum length cycle cover problem with further merging of cycles in the cover into a hamiltonian path. A cycle cover is a set of (simple) cycles such that each vertex in the graph is contained in exactly one cycle. The 

The cost of the minimum length cycle cover provides a lower bound on the length of TSP-tour. Since cycle cover for large graphs is hard to compute we used the following lower bound that is just slightly worse than the cycle cover  

---