Approximation results for kinetic variants of TSP
(2002) 26th International Colloquium, ICALP'99 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:
https://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
- conference dates
- 0001-01-02
- 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
- 2016-04-01 17:12:39
- date last changed
- 2022-02-05 21:29:41
@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}}, doi = {{10.1007/s00454-001-0081-4}}, volume = {{27}}, year = {{2002}}, }