Approximation results for kinetic variants of TSP
(2002) 26th International Colloquium, ICALP'99 27(4). p.635651 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:
http://lup.lub.lu.se/record/337251
 author
 Hammar, Mikael ^{LU} and Nilsson, BJ
 organization
 publishing date
 2002
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 host publication
 Discrete & Computational Geometry / Lecture Notes in Computer Science
 volume
 27
 issue
 4
 pages
 635  651
 publisher
 Springer
 conference name
 26th International Colloquium, ICALP'99
 conference location
 Prague, Czech Republic
 external identifiers

 wos:000175733400010
 scopus:0035999222
 ISSN
 01795376
 DOI
 10.1007/s0045400100814
 language
 English
 LU publication?
 yes
 id
 605f33f72f934755b1bbec37c7a27516 (old id 337251)
 alternative location
 http://www.springerlink.com/content/1xvq41w7tlpgdrc1
 date added to LUP
 20070823 11:10:48
 date last changed
 20190220 08:28:36
@inproceedings{605f33f72f934755b1bbec37c7a27516, 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}, issn = {01795376}, language = {eng}, location = {Prague, Czech Republic}, number = {4}, pages = {635651}, publisher = {Springer}, title = {Approximation results for kinetic variants of TSP}, url = {http://dx.doi.org/10.1007/s0045400100814}, volume = {27}, year = {2002}, }