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

Piotr Berman; Marek Karpinski

doi:10.1145/1109557.1109627

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

Piotr Berman, Marek Karpinski

Research output: Contribution to conference › Paper › peer-review

92 Scopus citations

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.

Original language	English (US)
Pages	641-648
Number of pages	8
DOIs	https://doi.org/10.1145/1109557.1109627
State	Published - 2006
Event	Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms - Miami, FL, United States Duration: Jan 22 2006 → Jan 24 2006

Other

Other	Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms
Country/Territory	United States
City	Miami, FL
Period	1/22/06 → 1/24/06

All Science Journal Classification (ASJC) codes

Software
General Mathematics

Access to Document

10.1145/1109557.1109627

Cite this

@conference{c127fd633ec846f4856b5626cf7bdba1,

title = "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.",

author = "Piotr Berman and Marek Karpinski",

year = "2006",

doi = "10.1145/1109557.1109627",

language = "English (US)",

pages = "641--648",

note = "Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 22-01-2006 Through 24-01-2006",

}

TY - CONF

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

AU - Berman, Piotr

AU - Karpinski, Marek

PY - 2006

Y1 - 2006

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=33244495766&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33244495766&partnerID=8YFLogxK

U2 - 10.1145/1109557.1109627

DO - 10.1145/1109557.1109627

M3 - Paper

AN - SCOPUS:33244495766

SP - 641

EP - 648

T2 - Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 22 January 2006 through 24 January 2006

ER -

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

Abstract

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this