04-11   Berichtsreihe des Mathematischen Seminars der Universität Kiel

Andreas Baltz, Anand Srivastav:

Approximation Algorithms for the Euclidean Bipartite TSP

We study approximation results for the Euclidean bipartite traveling salesman problem (TSP). We present the first worst-case examples, proving that the approximation guarantees of two known polynomial-time algorithms are tight. Moreover, we propose a new algorithm which displays a superior average case behavior indicated by computational experiments.

Mathematics Subject Classification (1991): 05C38, 68W25

Keywords: Euclidean bipartite TSP


Mail an Jens Burmeister
[Thu Feb 19 18:56:36 2009]
Impressum