Approximation algorithms for the Euclidean bipartite TSP |
| |
Authors: | Andreas Baltz Anand Srivastav |
| |
Institution: | Mathematisches Seminar, CAU Kiel, Christian-Albrechts-Platz 4, D-24098 Kiel, Germany |
| |
Abstract: | 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. |
| |
Keywords: | Euclidean bipartite TSP |
本文献已被 ScienceDirect 等数据库收录! |
|