New approximation results for the maximum scatter TSP

Yi J. Chiang

    Research output: Contribution to journalArticlepeer-review


    We consider the following maximum scatter traveling salesperson problem (TSP): given an edge-weighted complete graph G = (S, E), find a Hamiltonian path or cycle such that the length of a shortest edge is maximized. In other words, the goal is to have each point far away (most "scattered") from the points that are visited just before or just after it in the path/cycle. This is also referred to as the max-min 1-neighbor TSP. More generally, in the max-min m-neighbor TSP problem, the goal is to maximize the minimum distance between any point and all of its "m-neighbors" along the path/cycle. An m-neighbor of p is a point that is at most m points away from p in the path/cycle. These problems are closely related to the bottleneck TSP, and are motivated by applications in manufacturing (e.g., sequencing of rivet operations) and medical imaging. In this paper we give O(n2.5)-time approximation algorithms for the max-min 2-neighbor TSP with the triangle inequality. We achieve an approximation factor of 12 for the path version, and a factor of 18 for the cycle version of the problem, improving the previous best factors of 32 and 64, respectively [2], for all cases of n. Moreover, we present an O(m2.5)-time algorithm that achieves a constant approximation factor of 16 for the path version of the max-min m-neighbor TSP with the triangle inequality when n = (m + 1)k or when n = (m + 1)k + m, where m ∈ (2, n) is part of the inpur. This significantly improves the previous best approximation factor of 4 · 8⌈m/2⌉ [2], from exponential in m to a small constant.

    Original languageEnglish (US)
    Pages (from-to)309-341
    Number of pages33
    JournalAlgorithmica (New York)
    Issue number4
    StatePublished - Feb 2005


    • Approximation algorithms
    • Bottleneck tsp
    • Hamiltonian cycle/path
    • Matching
    • Maximum scatter tsp
    • Optimization
    • Traveling salesperson problem (Tsp)

    ASJC Scopus subject areas

    • General Computer Science
    • Computer Science Applications
    • Applied Mathematics


    Dive into the research topics of 'New approximation results for the maximum scatter TSP'. Together they form a unique fingerprint.

    Cite this