Approximation algorithms for TSP with neighborhoods in the plane

Adrian Dumitrescu; Joseph S.B. Mitchell

Approximation algorithms for TSP with neighborhoods in the plane

Adrian Dumitrescu
, Joseph S.B. Mitchell

Applied Mathematics and Statistics

Stony Brook University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

52 Scopus citations

Abstract

In the Euclidean TSP with neighborhoods (TSPN), we are given a collection of n regions (neighborhoods) and we seek a shortest tour that visits each region. As a generalization of the classical Euclidean TSP, TSPN is also NP-hard. In this paper, we present new approximation results for the TSPN, including (1) a constant-factor approximation algorithm for the case of arbitrary connected neighborhoods having comparable diameters; and (2) a PTAS for the important special case of disjoint unit disk neighborhoods (or nearly disjoint, nearly-unit disks). Our methods also yield improved approximation ratios for various special classes of neighborhoods, which have previously been studied. Further, we give a linear-time &Ogr;(1)-approximation algorithm for the case of neighborhoods that are (infinite) straight lines.

Original language	English
Title of host publication	Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms
Pages	38-46
Number of pages	9
State	Published - 2001
Event	2001 Operating Section Proceedings, American Gas Association - Dallas, TX, United States Duration: Apr 30 2001 → May 1 2001

Publication series

Name	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Conference

Conference	2001 Operating Section Proceedings, American Gas Association
Country/Territory	United States
City	Dallas, TX
Period	04/30/01 → 05/1/01

Keywords

Adaptive meshing
Algorithms
Computational geometry
Deformation
Differential geometry
Metamorphoses
Proofs

Cite this

@inproceedings{6c6c88a82f1842788e4c1d349260c3f4,

title = "Approximation algorithms for TSP with neighborhoods in the plane",

abstract = "In the Euclidean TSP with neighborhoods (TSPN), we are given a collection of n regions (neighborhoods) and we seek a shortest tour that visits each region. As a generalization of the classical Euclidean TSP, TSPN is also NP-hard. In this paper, we present new approximation results for the TSPN, including (1) a constant-factor approximation algorithm for the case of arbitrary connected neighborhoods having comparable diameters; and (2) a PTAS for the important special case of disjoint unit disk neighborhoods (or nearly disjoint, nearly-unit disks). Our methods also yield improved approximation ratios for various special classes of neighborhoods, which have previously been studied. Further, we give a linear-time \&Ogr;(1)-approximation algorithm for the case of neighborhoods that are (infinite) straight lines.",

keywords = "Adaptive meshing, Algorithms, Computational geometry, Deformation, Differential geometry, Metamorphoses, Proofs",

author = "Adrian Dumitrescu and Mitchell, \{Joseph S.B.\}",

year = "2001",

language = "English",

isbn = "0898714907",

series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

pages = "38--46",

booktitle = "Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms",

note = "2001 Operating Section Proceedings, American Gas Association ; Conference date: 30-04-2001 Through 01-05-2001",

}

Approximation algorithms for TSP with neighborhoods in the plane. / Dumitrescu, Adrian; Mitchell, Joseph S.B.
Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. 2001. p. 38-46 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Approximation algorithms for TSP with neighborhoods in the plane

AU - Dumitrescu, Adrian

AU - Mitchell, Joseph S.B.

PY - 2001

Y1 - 2001

N2 - In the Euclidean TSP with neighborhoods (TSPN), we are given a collection of n regions (neighborhoods) and we seek a shortest tour that visits each region. As a generalization of the classical Euclidean TSP, TSPN is also NP-hard. In this paper, we present new approximation results for the TSPN, including (1) a constant-factor approximation algorithm for the case of arbitrary connected neighborhoods having comparable diameters; and (2) a PTAS for the important special case of disjoint unit disk neighborhoods (or nearly disjoint, nearly-unit disks). Our methods also yield improved approximation ratios for various special classes of neighborhoods, which have previously been studied. Further, we give a linear-time &Ogr;(1)-approximation algorithm for the case of neighborhoods that are (infinite) straight lines.

AB - In the Euclidean TSP with neighborhoods (TSPN), we are given a collection of n regions (neighborhoods) and we seek a shortest tour that visits each region. As a generalization of the classical Euclidean TSP, TSPN is also NP-hard. In this paper, we present new approximation results for the TSPN, including (1) a constant-factor approximation algorithm for the case of arbitrary connected neighborhoods having comparable diameters; and (2) a PTAS for the important special case of disjoint unit disk neighborhoods (or nearly disjoint, nearly-unit disks). Our methods also yield improved approximation ratios for various special classes of neighborhoods, which have previously been studied. Further, we give a linear-time &Ogr;(1)-approximation algorithm for the case of neighborhoods that are (infinite) straight lines.

KW - Adaptive meshing

KW - Algorithms

KW - Computational geometry

KW - Deformation

KW - Differential geometry

KW - Metamorphoses

KW - Proofs

UR - https://www.scopus.com/pages/publications/26444452310

M3 - Conference contribution

AN - SCOPUS:26444452310

SN - 0898714907

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 38

EP - 46

BT - Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms

T2 - 2001 Operating Section Proceedings, American Gas Association

Y2 - 30 April 2001 through 1 May 2001

ER -

Approximation algorithms for TSP with neighborhoods in the plane

Abstract

Publication series

Conference

Keywords

Other files and links

Fingerprint

Cite this