A fast approximation algorithm for TSP with neighborhoods and redblue separation
(1999) 5th annual international conference, COCOON '99 In Computing and combinatorics / Lecture notes in computer science 1627. p.473482 Abstract
 In TSP with neighborhoods (TSPN) we are given a collection X of k polygonal regions, called neighborhoods, with totally n vertices, and we seek the shortest tour that visits each neighborhood. TheEuclidean TSP is a special case of the TSPN problem, so TSPN is alsoNPhard. 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 optimum 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... (More)
 In TSP with neighborhoods (TSPN) we are given a collection X of k polygonal regions, called neighborhoods, with totally n vertices, and we seek the shortest tour that visits each neighborhood. TheEuclidean TSP is a special case of the TSPN problem, so TSPN is alsoNPhard. 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 optimum 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. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/526595
 author
 Levcopoulos, Christos ^{LU} and Gudmundsson, Joachim
 organization
 publishing date
 1999
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 in
 Computing and combinatorics / Lecture notes in computer science
 editor
 Asano, Takano
 volume
 1627
 pages
 473  482
 publisher
 Springer
 conference name
 5th annual international conference, COCOON '99
 external identifiers

 Scopus:84957811036
 DOI
 10.1007/3540486860_47
 language
 English
 LU publication?
 yes
 id
 9454ea761963430a8038b10ea9e2837b (old id 526595)
 date added to LUP
 20070921 11:33:27
 date last changed
 20170101 08:04:48
@inproceedings{9454ea761963430a8038b10ea9e2837b, abstract = {In TSP with neighborhoods (TSPN) we are given a collection X of k polygonal regions, called neighborhoods, with totally n vertices, and we seek the shortest tour that visits each neighborhood. TheEuclidean TSP is a special case of the TSPN problem, so TSPN is alsoNPhard. 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 optimum 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.}, author = {Levcopoulos, Christos and Gudmundsson, Joachim}, booktitle = {Computing and combinatorics / Lecture notes in computer science}, editor = {Asano, Takano}, language = {eng}, pages = {473482}, publisher = {Springer}, title = {A fast approximation algorithm for TSP with neighborhoods and redblue separation}, url = {http://dx.doi.org/10.1007/3540486860_47}, volume = {1627}, year = {1999}, }