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.
|Research areas and keywords
|Title of host publication||Discrete & Computational Geometry / Lecture Notes in Computer Science|
|Publication status||Published - 2002|
|Event||26th International Colloquium, ICALP'99 - Prague, Czech Republic|
Duration: 0001 Jan 2 → …
|Conference||26th International Colloquium, ICALP'99|
|Period||0001/01/02 → …|