Improvement and Implementation of a Polynomial Time Approximation Scheme for Euclidean Traveling Salesman Problem

In the traveling salesman problem(“TSP” for short), given n nodes and for each pair i,j of distinct nodes, a distance d\-\i,j\, it desires a closed path that visits each node exactly once and incurs the least cost, which is the sum of the distances along the path. Traveling salesman problem is a NP-hard combinatorial optimization problem, and one of hot topics in computer algorithm field. The classic problem has proved a rich testing ground for most important algorithmic ideas during the past few decades, and influenced the emergence of fields such as polyhedral theory and complexity theory. However, exact optimization for TSP is NP-hard. So is approximating the optimum within any constant factor. TSP instances arising in practice are usually quite special, so the hardness result may not necessarily apply to them. In Euclidean TSP, the nodes lie in R\+\2\and distance is defined using the l\-\2\ norm. However, even Euclidean TSP is NP-hard. In 1996, S. Arora gave the first polynomial time approximation scheme (“PTAS”, for short) for this problem. An improvement on this scheme is proposed by reducing the constant in the so-called “patching lemma” from 6 to 3. At the same time, an implementation of the improved version is given.