A multi-matching approximation algorithm for Symmetric Traveling Salesman Problem

This paper presents a deterministic algorithm for approximating the solution of the Symmetric Traveling Salesman Problem (STSP) using a multi perfect matching and partitioning technique. Initially, we find the minimum cost collection of sub-tours that cover all cities, such that each sub-tour consists of at least four edges. The obtained solution is then partitioned into k branches, where k is the length of the smallest sub-tour in the resulting solution. The algorithm solves the sub-problems in parallel and selects the sub-problem with the minimum resulting cost to be partitioned further. The algorithm converges when a complete cycle without sub-tours is found. The performance of the proposed algorithm is evaluated and compared with the optimal values obtained by some well-known algorithms for solving STSP using 24 instances from the TSPLIB online library. The results of the experiments carried out in this study show that our approach yields optimum or near-optimum solutions in polynomial execution time.