Approximation algorithms for the Euclidean bipartite traveling salesman problem

Approximation algorithms for the Euclidean bipartite traveling salesman problem

0.00 Avg rating0 Votes
Article ID: iaor20061024
Country: Netherlands
Volume: 33
Issue: 4
Start Page Number: 403
End Page Number: 410
Publication Date: Jul 2005
Journal: Operations Research Letters
Authors: ,
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.

Reviews

Required fields are marked *. Your email address will not be published.