"An n log n Heuristic for the TSP" Éric Taillard An n log n randomized method based on POPMUSIC meta-heuristic is proposed for generating reasonably good solutions to the traveling salesman problem. The method improves a previous work which algorithmic complexity was in n^1.6. The method has been tested on instances with billions of cities. Few dozens of runs are able to generate a very high proportion of the edges of the best solutions known. This characteristic is exploited in a new release of the Helsgaun's implementation of Lin-Kernighan heuristic (LKH).