On the maximum scatter TSP

Esther M. Arkin; Yi Jen Chiang; Joseph S.B. Mitchell; Steven S. Skiena; Tae Cheon Yang

On the maximum scatter TSP

Esther M. Arkin, Yi Jen Chiang, Joseph S.B. Mitchell, Steven S. Skiena, Tae Cheon Yang

Research output: Contribution to conference › Paper › peer-review

Abstract

We study the problem of computing a Hamiltonian tour (cycle) or path on a set of points in order to maximize the minimum edge length in the tour or path. This `maximum scatter' TSP is closely related to the bottleneck TSP, and is motivated by applications in manufacturing (e.g., sequencing of rivet operations) and medical imaging. In this paper, we give the first algorithmic study of these problems, including complexity results, approximation algorithms, and exact algorithms for special cases. In an attempt to model more accurately the real problems that arise in practice, we also generalize the basic problem to consider a more general measure of `scatter' in which points on a tour or path should be far not only from their immediate predecessor and successor, but also from other near-neighbors along the tour or path.

Original language	English (US)
Pages	211-220
Number of pages	10
State	Published - 1997
Event	Proceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA, USA Duration: Jan 5 1997 → Jan 7 1997

Other

Other	Proceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms
City	New Orleans, LA, USA
Period	1/5/97 → 1/7/97

ASJC Scopus subject areas

Software
General Mathematics

Cite this

@conference{ac1fb25d1d304da19089d9a61b54fb4e,

title = "On the maximum scatter TSP",

abstract = "We study the problem of computing a Hamiltonian tour (cycle) or path on a set of points in order to maximize the minimum edge length in the tour or path. This `maximum scatter' TSP is closely related to the bottleneck TSP, and is motivated by applications in manufacturing (e.g., sequencing of rivet operations) and medical imaging. In this paper, we give the first algorithmic study of these problems, including complexity results, approximation algorithms, and exact algorithms for special cases. In an attempt to model more accurately the real problems that arise in practice, we also generalize the basic problem to consider a more general measure of `scatter' in which points on a tour or path should be far not only from their immediate predecessor and successor, but also from other near-neighbors along the tour or path.",

author = "Arkin, {Esther M.} and Chiang, {Yi Jen} and Mitchell, {Joseph S.B.} and Skiena, {Steven S.} and Yang, {Tae Cheon}",

year = "1997",

language = "English (US)",

pages = "211--220",

note = "Proceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 05-01-1997 Through 07-01-1997",

}

TY - CONF

T1 - On the maximum scatter TSP

AU - Arkin, Esther M.

AU - Chiang, Yi Jen

AU - Mitchell, Joseph S.B.

AU - Skiena, Steven S.

AU - Yang, Tae Cheon

PY - 1997

Y1 - 1997

N2 - We study the problem of computing a Hamiltonian tour (cycle) or path on a set of points in order to maximize the minimum edge length in the tour or path. This `maximum scatter' TSP is closely related to the bottleneck TSP, and is motivated by applications in manufacturing (e.g., sequencing of rivet operations) and medical imaging. In this paper, we give the first algorithmic study of these problems, including complexity results, approximation algorithms, and exact algorithms for special cases. In an attempt to model more accurately the real problems that arise in practice, we also generalize the basic problem to consider a more general measure of `scatter' in which points on a tour or path should be far not only from their immediate predecessor and successor, but also from other near-neighbors along the tour or path.

AB - We study the problem of computing a Hamiltonian tour (cycle) or path on a set of points in order to maximize the minimum edge length in the tour or path. This `maximum scatter' TSP is closely related to the bottleneck TSP, and is motivated by applications in manufacturing (e.g., sequencing of rivet operations) and medical imaging. In this paper, we give the first algorithmic study of these problems, including complexity results, approximation algorithms, and exact algorithms for special cases. In an attempt to model more accurately the real problems that arise in practice, we also generalize the basic problem to consider a more general measure of `scatter' in which points on a tour or path should be far not only from their immediate predecessor and successor, but also from other near-neighbors along the tour or path.

UR - http://www.scopus.com/inward/record.url?scp=0030823077&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0030823077&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:0030823077

SP - 211

EP - 220

T2 - Proceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 5 January 1997 through 7 January 1997

ER -

On the maximum scatter TSP

Abstract

Other

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this