kirk@speedy.cs.pitt.edu (Kirk Pruhs) (12/03/90)
In their 1977 SIAM J. of Comp. paper Rosendrantz, Stearns and Lewis proved that any insertion method for computing a tour in a metric space guaranteed a tour of weight at most O(log n) times the optimum. They further stated that this bound may not be tight in that they knew of no insertion method that created a tour more than a constant times the optimum tour. Does anyone know whether this problem has been resolved? Does every insertion algorithm guarantee a constant approximation? I am primarily interested in the Euclidean plane. DEFINITIONS: An insertion method creates a tour one point at a time. Each new point x is inserted between the two points b and c already in the tour that minimize d(b,x)+d(c,x)-d(b,c), the cost of adding x between b and c in the tour. Thus the order that the points are considered completely determines the resulting tour (ignoring the possibility of ties). Different insertion methods arise from the order in which the untraversed points are considered. For example, Nearest Insertion and Cheapest Insertion guarantee that the resulting tour is with a factor of 2 of the optimal tour. Thanks, Kirk Pruhs kirk@cs.pitt.edu