Path: utzoo!attcan!utgpu!news-server.csri.toronto.edu!rutgers!uwm.edu!rpi!zaphod.mps.ohio-state.edu!unix.cis.pitt.edu!pitt!speedy.cs.pitt.edu!kirk
From: kirk@speedy.cs.pitt.edu (Kirk Pruhs)
Newsgroups: comp.theory
Subject: Insertion Methods for TSP
Message-ID: <9420@pitt.UUCP>
Date: 2 Dec 90 18:31:13 GMT
Sender: news@pitt.UUCP
Reply-To: kirk@cs.pitt.edu.UUCP (Kirk Pruhs)
Organization: Univ. of Pittsburgh Computer Science
Lines: 23

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


Brought to you by Super Global Mega Corp .com