Malmö University Publications
Change search
Refine search result
1 - 1 of 1
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
  • 1. Hammar, Mikael
    et al.
    Nilsson, Bengt J
    Malmö högskola, School of Technology (TS).
    Approximation Results for Kinetic Variants of TSP2002In: Discrete & Computational Geometry, ISSN 0179-5376, E-ISSN 1432-0444, Vol. 27, no 4, p. 635-651Article in journal (Refereed)
    Abstract [en]

    We study the approximation complexity of certain kinetic variants of the Traveling Salesman Problem where we consider instances where points move with fixed constant velocity in a fixed direction. We prove the following results: 1. If the points all move with the same velocity and in the same direction, then there is a PTAS for the Kinetic TSP. 2. The Kinetic TSP cannot be approximated better than by a factor of two by a polynomial time algorithm unless P=NP, even if there are only two moving points in the instance. \item The Kinetic TSP cannot be approximated better than by a factor of $2^{\Omega(\sqrt{n})}$ by a polynomial time algorithm unless P=NP, where $n$ is the size of the input instance, even if the maximum velocity is bounded.

    Download full text (pdf)
    FULLTEXT01
1 - 1 of 1
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf