Approximation algorithms for Euclidean group TSP

Khaled Elbassioni; Aleksei V. Fishkin; Nabil H. Mustafa; René Sitters

doi:10.1007/11523468_90

Approximation algorithms for Euclidean group TSP

Khaled Elbassioni, Aleksei V. Fishkin, Nabil H. Mustafa, René Sitters

Electrical Engineering

Max-Planck-Institut für Informatik

Research output: Contribution to journal › Conference article › peer-review

53 Scopus citations

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	https://doi.org/10.1007/11523468_90
State	Published - 2005
Event	32nd International Colloquium on Automata, Languages and Programming, ICALP 2005 - Lisbon, Portugal Duration: 11 Jul 2005 → 15 Jul 2005

Access to Document

10.1007/11523468_90

Cite this

@article{bab30fdc83bd4d0b98f9cee2c9796570,

title = "Approximation algorithms for Euclidean group TSP",

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.",

author = "Khaled Elbassioni and Fishkin, {Aleksei V.} and Mustafa, {Nabil H.} and Ren{\'e} Sitters",

year = "2005",

doi = "10.1007/11523468_90",

language = "British English",

volume = "3580",

pages = "1115--1126",

journal = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

issn = "0302-9743",

publisher = "Springer Science and Business Media Deutschland GmbH",

note = "32nd International Colloquium on Automata, Languages and Programming, ICALP 2005 ; Conference date: 11-07-2005 Through 15-07-2005",

}

TY - JOUR

T1 - Approximation algorithms for Euclidean group TSP

AU - Elbassioni, Khaled

AU - Fishkin, Aleksei V.

AU - Mustafa, Nabil H.

AU - Sitters, René

PY - 2005

Y1 - 2005

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=26444564642&partnerID=8YFLogxK

U2 - 10.1007/11523468_90

DO - 10.1007/11523468_90

M3 - Conference article

AN - SCOPUS:26444564642

SN - 0302-9743

VL - 3580

SP - 1115

EP - 1126

JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

T2 - 32nd International Colloquium on Automata, Languages and Programming, ICALP 2005

Y2 - 11 July 2005 through 15 July 2005

ER -

Approximation algorithms for Euclidean group TSP

Abstract

Access to Document

Other files and links

Fingerprint

Cite this