Approximation algorithms for Euclidean group TSP

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

    Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

    47 Citaten (Scopus)
    2 Downloads (Pure)


    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.
    Originele taal-2Engels
    TitelAutomata, languages and programming : 32nd international colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005. : proceedings
    RedacteurenL. Caires, G.F. Italiano, L. Monteiro, C. Palamidessi, M. Yung
    Plaats van productieBerlin
    ISBN van geprinte versie3-540-27580-0
    StatusGepubliceerd - 2005

    Publicatie series

    NaamLecture Notes in Computer Science
    ISSN van geprinte versie0302-9743


    Duik in de onderzoeksthema's van 'Approximation algorithms for Euclidean group TSP'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit