Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: Feb 24, 2000 12:48 AM Subject: Re: Travelling Salesman Problem >1. Assume we are given a set of cities AND the optimal tour for those >cities. If we move ONE point ... I'm afraid I haven't got an answer to this question, though I can imagine you may be able to show it is NP-hard by reducing it to changing a single variable in a SAT problem. Of course, this doesn't show it is TSP-hard (since Euclidean TSP is not known to be in NP). > If this can't be shown true for ANY new location of the given >point, does anyone know if there exists some f(Theta) = Delta -- >(Theta being the angle that the point will be moved at, and Delta >being the distance it is moved) such that the optimal tour is >unchanged?.... The "angle that the point will be moved at" with respect to what? I suspect some widget can be constructed in which a point is arbitrarily close to some critical location that changes the tour in some huge and nonobvous way. >2. If a tour can be constructed that forms an entirely convex figure >(I don't know if this is the right word, what I mean is that all the >interior angles are <= 180), can say that must be the optimal tour? Yes. When the points are all on their convex hull, the optimal tour is the convex hull taken in order. Any other order would cause edges to cross, which is easily seen to be suboptimal. Dan Hoey (posted and e-mailed)