Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-APX-Reports 2006 Copyright 2006 University of Bonn, Department of Computer Science, Abt. V
89102

10.05.2006

8/7-Approximation Algorithm for (1,2)-TSP (Extended Version)
Piotr Berman and Marek Karpinski
[Download PostScript] [Download PDF]

We design a polynomial time 8/7-approximation algorithm for theTraveling Salesman Problem in which all distances areeither one or two. This improves over the best known approximationfactor for that problem. As a direct application we get a7/6-approximation algorithm for the Maximum Path Cover Problem,similarly improving upon the best known approximation factorfor that problem. The result depends on a new method of consecutivepath cover improvements and on a new analysis of certain related coloralternating paths. This method could be of independent interest.

Last Change: 11/05/14 at 10:36:57
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V