A 1.5-Approximation for Symmetric Euclidean Open Loop TSP

Abstract

Travelling Salesman Problem (TSP) is NP-hard and therefore lacks efficient algorithm that provides optimal solution. So far, a benchmark in this area is Christofides’ Algorithm, which provides an upper bound of 3/2 for metric TSP. In this paper, it is shown that a simple nearest neighbor heuristic called 2- Repetitive Nearest Neighbor (2-RNN) with much simpler implementation without the need to construct minimum spanning tree and Euler tour also has the approximation ratio of 3/2 for open loop symmetric Euclidean TSP which also matches with current standard for open loop TSP. Experiments also show that the average performance of 2-RNN in terms of gap percentage (18.75) is better than that of Christofides’ algorithm (28.09) for eight instances of TSPLIB dataset and gap percentage of 1.06 (2-RNN) and 9.10 (Christofides) for 6449 instances of the Dots dataset, albeit at the cost of an order of magnitude higher time complexity.

Keywords

• Christofides’ algorithm
• 5-degree minimum spanning tree
• 3-degree spanning tree
• approximation ratio
• symmetric euclidean TSP
• 2-RNN