Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2002 | 10.1007/s00454-001-0081-4 | DISCRETE & COMPUTATIONAL GEOMETRY |
DocType | Volume | Issue |
Journal | 27 | 4 |
ISSN | Citations | PageRank |
0179-5376 | 1 | 0.37 |
References | Authors | |
0 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Mikael Hammar | 1 | 163 | 16.22 |
Bengt J. Nilsson | 2 | 210 | 24.43 |