next up previous
Next: General Metric TSP *

Approximation Taxonomy of Metric TSP

Editors:
M. Hauptmann  and M. Karpinski


Department of Computer Science and
Hausdorff Center for Mathematics
University of Bonn





The list below presents the best up to now known upper and lower approximation bounds for the instances of metric TSP (we refer also to another source on approximation algorithms for metric TSP [8]). It is intended to codify (at one glance) the (many) recent developments and improvements on the approximability of that problem. It is hoped to be useful in further research on the possible improvements of the underlying approximation bounds.


Dept. of Computer Science,
University of Bonn
Email: tsp@cs.uni-bonn.de





2015-04-14 Revision: 286 PDF version