Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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

Levcopoulos, Christos LU orcid and Gudmundsson, Joachim (1999) 5th annual international conference, COCOON '99 1627. p.473-482
Abstract
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... (More)
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. (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
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
conference location
Tokyo, Japan
conference dates
1999-07-26 - 1999-07-28
external identifiers
  • scopus:84957811036
DOI
10.1007/3-540-48686-0_47
language
English
LU publication?
yes
id
9454ea76-1963-430a-8038-b10ea9e2837b (old id 526595)
date added to LUP
2016-04-04 11:42:22
date last changed
2022-03-23 18:04:37
@inproceedings{9454ea76-1963-430a-8038-b10ea9e2837b,
  abstract     = {{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.}},
  author       = {{Levcopoulos, Christos and Gudmundsson, Joachim}},
  booktitle    = {{Computing and combinatorics / Lecture notes in computer science}},
  editor       = {{Asano, Takano}},
  language     = {{eng}},
  pages        = {{473--482}},
  publisher    = {{Springer}},
  title        = {{A fast approximation algorithm for TSP with neighborhoods and red-blue separation}},
  url          = {{https://lup.lub.lu.se/search/files/5836087/623758.pdf}},
  doi          = {{10.1007/3-540-48686-0_47}},
  volume       = {{1627}},
  year         = {{1999}},
}