A fairly wellknown heuristic for TSP that is based on matching is described in the 2003 paper Match twice and stitch: a new TSP tour construction heuristic by Andrew B. Kahng and Sherief Reda.
Its basic idea is to generate a vertex-covering collection of even cycles via the union of two edge-disjoint matchings and then striving to optimally combine the cycles to arrive at a short Hamilton cycle.
The performance of that heuristic is reportedly good.
My question is however related to a different idea of "directly" constructing short Hamilton cycles of a graph with $n=2^k$ vertices by starting with a minimum weight matching, defining the matching edges to be the "root-paths" having level $0$. The paths of the next level are then generated by optimally connecting pairs of paths from the previous level and to finally insert the edge that connects the ends of the final path. That idea has already been pursued in the 1996 German phd thesis *Traveling Salesman Problem mit iteriertem Matching* (Traveling Salesman Problem via Iterated Matching) by Frank Lauxtermann.
That paper is however the only one I could find where the idea of repeatedly combining pairs of paths at minimal cost is mentionend and apart from that the algorithm in the cited paper left a fuzzy impression on me in the sense that the combination of paths is based on rather involved criteria that aim at yielding low-weight combinations.
Questions:
- has the idea to repeatedly combining pairs of paths (starting with the set of edges in a matching) also been investigated by other authors?
- what is known about algorithms for determining the pairs of paths whose optimal combination yields the optimal solution of reducing the number of paths from $2m$ to $m$?
