Quasi-linear time heuristic to solve the Euclidean traveling salesman problem with low gap

The traveling salesman problem (TSP) is a well studied NP-hard optimization problem. We present a novel heuristic to find approximate solutions for the case of the TSP with Euclidean metric. Our pair-center algorithm runs in quasi-linear time and on linear space. In practical experiments on a variety of well known benchmarks the algorithm shows linearithmic (i.e., O(n ( n log n ) ) runtime. The solutions found by the pair-center algorithm are very good on smaller problem instances, and better than those generated by any other heuristic with at most quadratic runtime. Eventually, the average gap of the pair-center algorithm on all benchmark instances with less than 1001 points is 0.94% and for all instances with more than 1000 points up to 100 million points is 4.57%.