THE TRAVELING SALESMAN PROBLEM WITH DISTANCES ONE AND 2

被引：235

作者：

PAPADIMITRIOU, CH ^{[1
]}

YANNAKAKIS, M ^{[1
]}

机构：

[1] AT&T BELL LABS,MURRAY HILL,NJ 07974

来源：

MATHEMATICS OF OPERATIONS RESEARCH | 1993年 / 18卷 / 01期

关键词：

TRAVELING SALESMAN; COMPUTATIONAL COMPLEXITY; POLYNOMIAL-TIME ALGORITHMS;

D O I：

10.1287/moor.18.1.1

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

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.

引用

页码：1 / 11

页数：11