THE TRAVELING SALESMAN PROBLEM WITH DISTANCES ONE AND 2
成果类型：
Article
署名作者：
PAPADIMITRIOU, CH; YANNAKAKIS, M
署名单位：
Nokia Corporation; Nokia Bell Labs; AT&T
刊物名称：
MATHEMATICS OF OPERATIONS RESEARCH
ISSN/ISSBN：
0364-765X
DOI：
10.1287/moor.18.1.1
发表日期：
1993
页码：
1-11
关键词：
摘要：
We present a polynomial-time approximation algorithm with worst-case ratio 7/6 for the special case of the traveling salesman problem in which all distances are either one or two. We also show that this special case of the traveling salesman problem is MAX SNP-hard, and therefore it is unlikely that it has a polynomial-time approximation scheme.
来源URL：