On the approximability of the traveling salesman problem

被引：48
|
作者：
Papadimitriou, CH [1 ]
Vempala, S
机构：
[1] Univ Calif Berkeley, Comp Sci Div, Berkeley, CA 94720 USA
[2] MIT, Dept Math, Cambridge, MA 02139 USA
来源：
COMBINATORICA | 2006年 / 26卷 / 01期
基金：
美国国家科学基金会;
关键词：
D O I：
10.1007/s00493-006-0008-z
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
We show that the traveling salesman problem with triangle inequality cannot be approximated with a ratio better than (117)/(116) when the edge lengths are allowed to be asymmetric and (220)/(219) when the edge lengths are symmetric, unless P=NP. The best previous lower bounds were (2805)/(2804) and (3813)/(3812) respectively. The reduction is from Hastad's maximum satisfiability of linear equations modulo 2, and is nonconstructive.
引用
收藏
页码：101 / 120
页数：20
相关论文
共 50 条
  • [21] AN ALGORITHM FOR THE TRAVELING SALESMAN PROBLEM
    LITTLE, JDC
    MURTY, KG
    SWEENEY, DW
    KAREL, C
    OPERATIONS RESEARCH, 1963, 11 (06) : 972 - 989
  • [22] NOTE ON TRAVELING SALESMAN PROBLEM
    JONES, L
    SIAM JOURNAL ON APPLIED MATHEMATICS, 1977, 32 (01) : 220 - 222
  • [23] A NOTE ON THE TRAVELING SALESMAN PROBLEM
    CHVATAL, V
    OPERATIONS RESEARCH LETTERS, 1989, 8 (02) : 77 - 78
  • [24] Linearity in the traveling salesman problem
    Colletti, BW
    Barnes, JW
    APPLIED MATHEMATICS LETTERS, 2000, 13 (03) : 27 - 32
  • [25] Risky traveling salesman problem
    Papadakos, Nikolaos
    Tzallas-Regas, George
    Rustem, Berc
    Thoms, Joanne
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2011, 212 (01) : 69 - 73
  • [26] A RELATIVISTIC TRAVELING SALESMAN PROBLEM
    OKEEFE, R
    AMERICAN JOURNAL OF PHYSICS, 1984, 52 (06) : 565 - 565
  • [27] DIRECTED TRAVELING SALESMAN PROBLEM
    CHAKRABARTI, BK
    JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL, 1986, 19 (07): : 1273 - 1275
  • [28] Colored Traveling Salesman Problem
    Li, Jun
    Zhou, MengChu
    Sun, Qirui
    Dai, Xianzhong
    Yu, Xiaolong
    IEEE TRANSACTIONS ON CYBERNETICS, 2015, 45 (11) : 2390 - 2401
  • [29] Traveling salesman problem of segments
    Xu, JH
    Yang, Y
    Lin, ZY
    COMPUTING AND COMBINATORICS, PROCEEDINGS, 2003, 2697 : 40 - 49
  • [30] Dynamic Traveling Salesman Problem
    Fabry, Jan
    PROCEEDINGS OF THE 24TH INTERNATIONAL CONFERENCE ON MATHEMATICAL METHODS IN ECONOMICS 2006, 2006, : 137 - 145
12345