Advanced

Approximation results for kinetic variants of TSP

Hammar, Mikael LU and Nilsson, BJ (2002) 26th International Colloquium, ICALP'99 In Discrete & Computational Geometry / Lecture Notes in Computer Science 27(4). p.635-651
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... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
Discrete & Computational Geometry / Lecture Notes in Computer Science
volume
27
issue
4
pages
635 - 651
publisher
Springer
conference name
26th International Colloquium, ICALP'99
external identifiers
  • wos:000175733400010
  • scopus:0035999222
ISSN
0179-5376
DOI
10.1007/s00454-001-0081-4
language
English
LU publication?
yes
id
605f33f7-2f93-4755-b1bb-ec37c7a27516 (old id 337251)
alternative location
http://www.springerlink.com/content/1xvq41w7tlpgdrc1
date added to LUP
2007-08-23 11:10:48
date last changed
2017-01-01 07:27:21
@inproceedings{605f33f7-2f93-4755-b1bb-ec37c7a27516,
  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.},
  author       = {Hammar, Mikael and Nilsson, BJ},
  booktitle    = {Discrete & Computational Geometry / Lecture Notes in Computer Science},
  issn         = {0179-5376},
  language     = {eng},
  number       = {4},
  pages        = {635--651},
  publisher    = {Springer},
  title        = {Approximation results for kinetic variants of TSP},
  url          = {http://dx.doi.org/10.1007/s00454-001-0081-4},
  volume       = {27},
  year         = {2002},
}