Journal
DISCRETE & COMPUTATIONAL GEOMETRY
Volume 27, Issue 4, Pages 635-651Publisher
SPRINGER
DOI: 10.1007/s00454-001-0081-4
Keywords
-
Categories
Ask authors/readers for more resources
We study the approximation complexity of certain kinetic variants of the Traveling Salesman Problem (TSP) where we consider instances in which each point moves with a fixed constant speed in a fixed direction. We prove the following results: 1. If the points all move with the same velocity, then there is a polynomial time approximation scheme for the Kinetic TSP. 2. The Kinetic TSP cannot be approximated better than by a factor of 2 by a polynomial time algorithm unless P = NP, even if there are only two moving points in the instance. 3. The Kinetic TSP cannot be approximated better than by a factor of 2(Omega(rootn)) by a polynomial time algorithm unless P = NP, even if the maximum velocity is bounded. n denotes the size of the input instance. The last result is especially surprising in the light of existing polynomial time approximation schemes for the static version of the problem.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available