A fast approximation algorithm for TSP with neighborhoods and red-blue separation

Christos Levcopoulos, Joachim Gudmundsson

    Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceedingpeer-review

    12 Citations (SciVal)

    Abstract

    In TSP with neighborhoods (TSPN) we are given a collec-tion X of k polygonal regions, called neighborhoods, with totally n ver-tices, and we seek the shortest tour that visits each neighborhood. TheEuclidean TSP is a special case of the TSPN problem, so TSPN is alsoNP-hard. In this paper we present a simple and fast algorithm that, givena start point, computes a TSPN tour of length O(log k) times the opti-mum in time O(n+k log k). When no start point is given we show howto compute a good start point in time O(n2 log n), hence we obtain alogarithmic approximation algorithm that runs in time O(n2 log n). Wealso present an algorithm which performs at least one of the followingtwo tasks (which of these tasks is performed depends on the given input):(1) It outputs in time O(n log n) a TSPN tour of length O(log k) timesthe optimum. (2) It outputs a TSPN tour of length less than (1+) timesthe optimum in cubic time, where is an arbitrary real constant givenas an optional parameter.The results above are signicant improvements, since the best previouslyknown logarithmic approximation algorithm runs in (n5) time in theworst case.
    Original languageEnglish
    Title of host publicationComputing and combinatorics / Lecture notes in computer science
    EditorsTakano Asano
    PublisherSpringer
    Pages473-482
    Volume1627
    DOIs
    Publication statusPublished - 1999
    Event5th annual international conference, COCOON '99 - Tokyo, Japan
    Duration: 1999 Jul 261999 Jul 28

    Publication series

    Name
    Volume1627

    Conference

    Conference5th annual international conference, COCOON '99
    Country/TerritoryJapan
    CityTokyo
    Period1999/07/261999/07/28

    Subject classification (UKÄ)

    • Computer Science

    Fingerprint

    Dive into the research topics of 'A fast approximation algorithm for TSP with neighborhoods and red-blue separation'. Together they form a unique fingerprint.

    Cite this