Approximation algorithms for Euclidean group TSP

K.M. Elbassioni, A.V. Fishkin, N.H. Mustafa, R.A. Sitters

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    43 Citations (Scopus)
    2 Downloads (Pure)

    Abstract

    In the Euclidean group Traveling Salesman Problem (TSP), we are given a set of points P in the plane and a set of m connected regions, each containing at least one point of P. We want to find a tour of minimum length that visits at least one point in each region. This unifies the TSP with Neighborhoods and the Group Steiner Tree problem. We give a (9.1a+1)-approximation algorithm for the case when the regions are disjoint a-fat objects with possibly varying size. This considerably improves the best results known, in this case, for both the group Steiner tree problem and the TSP with Neighborhoods problem. We also give the first O(1)-approximation algorithm for the problem with intersecting regions.
    Original languageEnglish
    Title of host publicationAutomata, languages and programming : 32nd international colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005. : proceedings
    EditorsL. Caires, G.F. Italiano, L. Monteiro, C. Palamidessi, M. Yung
    Place of PublicationBerlin
    PublisherSpringer
    Pages1115-1126
    ISBN (Print)3-540-27580-0
    DOIs
    Publication statusPublished - 2005

    Publication series

    NameLecture Notes in Computer Science
    Volume3580
    ISSN (Print)0302-9743

    Fingerprint

    Dive into the research topics of 'Approximation algorithms for Euclidean group TSP'. Together they form a unique fingerprint.

    Cite this