V. Bafna et al., NOT ALL INSERTION METHODS YIELD CONSTANT APPROXIMATE TOURS IN THE EUCLIDEAN PLANE, Theoretical computer science, 125(2), 1994, pp. 345-353
Citations number
12
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
An insertion heuristic for the traveling salesman problem adds cities
iteratively to an existing tour by replacing one edge with a two-edge
path through the new city in the cheapest possible way. Rosenkrantz et
al. (1977) asked whether every order of inserting vertices gives a co
nstant-factor approximation algorithm. We answer this question by show
ing that for some point sets, there is an order that yields tours with
length OMEGA(log n/log log n) times optimum, even if the underlying m
etric space is the Euclidean plane.