Approximation algorithms for Euclidean group TSP and TSP with neighborhoods

K.M. Elbassioni, A.V. Fishkin, R.A. Sitters

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

In the Euclidean traveling salesman problem with discrete neighborhoods, we are given a set of points P in the plane and a set of n connected regions (neighborhoods), each containing at least one point of P. We seek to find a tour of minimum length which visits at least one point in each region. We give (i) an O(α)-approximation algorithm for the case when the regions are disjoint and α-fat, with possibly varying size; (ii) an O(α
Original languageEnglish
Pages (from-to)173-193
JournalInternational Journal of Computational Geometry and Applications
Volume19
DOIs
Publication statusPublished - 2009

Fingerprint

Dive into the research topics of 'Approximation algorithms for Euclidean group TSP and TSP with neighborhoods'. Together they form a unique fingerprint.

Cite this