## 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.1α + 1)-approximation algorithm for the case when the regions are disjoint α-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 language | British English |
---|---|

Pages (from-to) | 1115-1126 |

Number of pages | 12 |

Journal | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |

Volume | 3580 |

DOIs | |

State | Published - 2005 |

Event | 32nd International Colloquium on Automata, Languages and Programming, ICALP 2005 - Lisbon, Portugal Duration: 11 Jul 2005 → 15 Jul 2005 |