Javascript verkar inte påslaget? - Vissa delar av Lunds universitets webbplats fungerar inte optimalt utan javascript, kontrollera din webbläsares inställningar.
Du är här

A fast approximation algorithm for TSP with neighborhoods and red-blue separation

  • Takano Asano
Publiceringsår: 1999
Språk: Engelska
Sidor: 473-482
Publikation/Tidskrift/Serie: Computing and combinatorics / Lecture notes in computer science
Volym: 1627
Dokumenttyp: Konferensbidrag
Förlag: Springer


In TSP with neighborhoods (TSPN) we are given a collec-tion X of k polygonal regions, called neighborhoods, with totally n ver-tices, and we seek the shortest tour that visits each neighborhood. TheEuclidean TSP is a special case of the TSPN problem, so TSPN is alsoNP-hard. In this paper we present a simple and fast algorithm that, givena start point, computes a TSPN tour of length O(log k) times the opti-mum in time O(n+k log k). When no start point is given we show howto compute a good start point in time O(n2 log n), hence we obtain alogarithmic approximation algorithm that runs in time O(n2 log n). Wealso present an algorithm which performs at least one of the followingtwo tasks (which of these tasks is performed depends on the given input):(1) It outputs in time O(n log n) a TSPN tour of length O(log k) timesthe optimum. (2) It outputs a TSPN tour of length less than (1+) timesthe optimum in cubic time, where is an arbitrary real constant givenas an optional parameter.The results above are signicant improvements, since the best previouslyknown logarithmic approximation algorithm runs in (n5) time in theworst case.


  • Computer Science


5th annual international conference, COCOON '99

Box 117, 221 00 LUND
Telefon 046-222 00 00 (växel)
Telefax 046-222 47 20
lu [at] lu [dot] se

Fakturaadress: Box 188, 221 00 LUND
Organisationsnummer: 202100-3211
Om webbplatsen