Optimization and parallelization of simplified Balas' and Christofides' algorithm for the traveling salesman problem

The paper describes an exact parallel algorithm for the traveling salesman problem based on simplified Balas' and Christofides' algorithm, its optimization, and improvements in its parallel efficiency. Due to the new method of passing tasks between parallel threads, the algorithm solves, on average, instances with 3000 nodes (with random edge weights) in 1 minute, and instances with 10000 nodes in 50 minutes. The algorithm can solve instances with more than 3000 nodes due to the memory usage optimization introduced in this paper.