ECCC-Report TR05-069https://eccc.weizmann.ac.il/report/2005/069Comments and Revisions published for TR05-069en-usThu, 01 Jun 2006 00:00:00 +0300
Revision 2
| 8/7-Approximation Algorithm for (1,2)-TSP* (Extended Version) |
Piotr Berman,
Marek Karpinski
https://eccc.weizmann.ac.il/report/2005/069#revision2We 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.
Thu, 01 Jun 2006 00:00:00 +0300https://eccc.weizmann.ac.il/report/2005/069#revision2
Revision 1
| 8/7-Approximation Algorithm for (1,2)-TSP |
Piotr Berman,
Marek Karpinski
https://eccc.weizmann.ac.il/report/2005/069#revision1We 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.
Wed, 16 Nov 2005 00:00:00 +0200https://eccc.weizmann.ac.il/report/2005/069#revision1
Paper TR05-069
| 8/7-Approximation Algorithm for (1,2)-TSP |
Piotr Berman,
Marek Karpinski
https://eccc.weizmann.ac.il/report/2005/069We 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.
Mon, 11 Jul 2005 16:35:59 +0300https://eccc.weizmann.ac.il/report/2005/069