Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Consistency:
TR05-069 | 11th July 2005
Piotr Berman, Marek Karpinski

8/7-Approximation Algorithm for (1,2)-TSP

Revisions: 2

We design a polynomial time 8/7-approximation algorithm for the Traveling Salesman Problem in which all distances are either one or two. This improves over the best known approximation factor of 7/6 for that problem. As a direct application we get a 7/6-approximation algorithm for the Maximum Path Cover Problem, similarily ... more >>>

ISSN 1433-8092 | Imprint