Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Approximation results for kinetic variants of TSP

Hammar, Mikael LU and Nilsson, BJ (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:
author
and
organization
publishing date
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}},
}