ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR05-069 | 1st June 2006 00:00

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

RSS-Feed

Abstract:

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 for that problem. As a direct application we get a 7/6-approximation algorithm for the Maximum Path Cover Problem,similarly improving upon the best known approximation factor for that problem. The result depends on a new method of consecutive path cover improvements and on a new analysis of certain related color alternating paths. This method could be of independent interest.


Revision #1 to TR05-069 | 16th November 2005 00:00

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


Abstract:

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 for that problem. As a direct application we get a 7/6-approximation algorithm for the Maximum Path Cover Problem,similarly improving upon the best known approximation factor for that problem. The result depends on a new method of consecutive path cover improvements and on a new analysis of certain related color alternating paths. This method could be of independent interest.


Paper:

TR05-069 | 11th July 2005 00:00

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


Abstract:

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 improving upon the best known approximation factor for that problem. The result depends on a new method of consecutive path cover improvements and on a new analysis of certain related color alternating paths. This method could be of independent
interest.



ISSN 1433-8092 | Imprint