Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-APX-Reports 2005 Copyright 2005 Universität Bonn, Institut für Informatik, Abt. V
8999

11.07.2005

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

We design a polynomial time 8/7-approximation algorithm forthe Traveling Salesman Problem in which all distances areeither one or two. This improves over the best known approximationfactor of 7/6 for that problem. As a direct application we get a7/6-approximation algorithm for the Maximum Path Cover Problem,similarily 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 independentinterest.

Last Change: 11/05/14 at 10:32:07
 English
Universität Bonn -> Institut für Informatik -> Abteilung V