NOT ALL INSERTION METHODS YIELD CONSTANT APPROXIMATE TOURS IN THE EUCLIDEAN PLANE

Citation
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
ISSN journal
03043975
Volume
125
Issue
2
Year of publication
1994
Pages
345 - 353
Database
ISI
SICI code
0304-3975(1994)125:2<345:NAIMYC>2.0.ZU;2-K
Abstract
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.