On the maximum scatter traveling salesperson problem

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

    Research output: Contribution to journalArticlepeer-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' traveling salesperson problem (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)
    Pages (from-to)515-544
    Number of pages30
    JournalSIAM Journal on Computing
    Issue number2
    StatePublished - 1999

    ASJC Scopus subject areas

    • General Computer Science
    • General Mathematics


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

    Cite this