04-11 | Berichtsreihe des Mathematischen Seminars der Universität Kiel | |
Andreas Baltz, Anand Srivastav:Approximation Algorithms for the Euclidean Bipartite TSPWe 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 |