Improvement And Implementation Of A Polynomial Time Approximation Scheme For Euclidean Traveling Salesman Problem

Designing approximation algorithms for NP — Hard problems is always the major work in computer theory field. The Traveling Salesman Problem ("TSP" for short) is a classic problem in the history of computer algorithm. It has proved a rich testing ground for most important algorithmic ideas during the past few decades, and influences the emergence of some fields such as polyhedral theory and complexity-theory.In TSP, we are given n nodes and for each pair {i,j} of distinct nodes, a distance d_i,j.We desire a closed path that visits each node exactly once and incurs the least cost, which is the sum of the distances along the path.Exact optimization for TSP is NP-hard. So is approximating the optimum within any constant factor. In Euclidean TSP the nodes lie in R² and distance is defined using the l₂ norm. But, even Euclidean TSP is NP-hard. And in 1996. Arora proposed the first PTAS for Euclidean TSP by using randomized partitioning and dynamic programming.In the paper, we introduce the method of designing PTAS for Euclidean TSP by using randomized partitioning and dynamic programming. Then we propose an improvement on this scheme by reducing the constant g in the so-called ''Patching Lemma" from 6 to 3. By reducing the value of g, we can make the value of m, r in the algorithm decrease, so that we can make the time of the algorithm decrease. At the same time, we give an implementation of the improved version. And we use 3 instances in the TSPLIB to test the algorithm. And by analyzing the result, we propose that we can improve the algorithm from the following aspects: first, we can use pruning technique in dynamic programming; second, we can design the parallel implementation of dynamic programming.