Approximation results for kinetic variants of TSP

Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceeding

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.

Details

Authors
  • Mikael Hammar
  • BJ Nilsson
Research areas and keywords

Subject classification (UKÄ)

  • Computer Science
Original languageEnglish
Title of host publicationDiscrete & Computational Geometry / Lecture Notes in Computer Science
PublisherSpringer
Pages635-651
Volume27
Publication statusPublished - 2002
Publication categoryResearch
Peer-reviewedYes
Event26th International Colloquium, ICALP'99 - Prague, Czech Republic
Duration: 0001 Jan 2 → …

Publication series

Name
Number4
Volume27
ISSN (Print)0179-5376

Conference

Conference26th International Colloquium, ICALP'99
Country/TerritoryCzech Republic
CityPrague
Period0001/01/02 → …