The parallel complexity of TSP Heuristics

The authors consider eight heuristics for constructing approximate solutions to the traveling salesman problem and analyze their complexity in a model of parallel computation. The problems of finding a tour by the nearest neighbor, nearest merger, nearest insertion, cheapest insertion, and farthest insertion heuristics are shown to be 𝒫-complete. Hence, it is unlikely that such tours can be obtained in polylogarithmic work space on a sequential computer or in polylogarithmic time on a computer with unbounded parallelism. The double minimum spanning tree and nearest addition heuristics can be implemented to run in polylogarithmic time on a polynomial number of processors. For the Christofides heuristic, the authors give a randomized polylogarithmic approximation scheme requiring a polynomial number of processors.