A Note on the Largest Insertion Algorithm for the Traveling Salesman Problem

Nearest, Farthest, and Cheapest Insertion are three well-known polynomial-time approximation algorithms for the Traveling Salesman Problem (TSP). This paper aims to report on a fourth insertion algorithm, called Largest Insertion, from both a theoretical and an experimental viewpoint. On the theoretical side, the worst-case performance of the algorithm is studied: In particular, it is shown that there exist instances for which the value of the solution computed by Largest Insertion approaches three times the optimum in the Euclidean plane. On the experimental side, the outcome of computational tests is reported: When compared with the other three insertion algorithms, Largest Insertion scores second on random Euclidean instances and first on large random graphical instances.