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 conferencePaperpeer-review


    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 languageEnglish (US)
    Number of pages10
    StatePublished - 1997
    EventProceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA, USA
    Duration: Jan 5 1997Jan 7 1997


    OtherProceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms
    CityNew Orleans, LA, USA

    ASJC Scopus subject areas

    • Software
    • General Mathematics


    Dive into the research topics of 'On the maximum scatter TSP'. Together they form a unique fingerprint.

    Cite this