On the integrality ratio for the asymmetric traveling salesman problem

被引：24
|
作者：
Charikar, Moses
Goemans, Michel X.
Karloff, Howard
机构：
[1] Princeton Univ, Dept Comp Sci, Princeton, NJ 08540 USA
[2] MIT, Dept Math, Cambridge, MA 02139 USA
[3] AT&T Labs Res, Florham Pk, NJ 07932 USA
来源：
MATHEMATICS OF OPERATIONS RESEARCH | 2006年 / 31卷 / 02期
关键词：
asymmetric traveling salesman problem; Held-Karp relaxation; integrality ratio; approximation algorithm; ATSP;
D O I：
10.1287/moor.1060.0191
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
We improve the lower bound on the integrality ratio of the Held-Karp bound for asymmetric TSP with triangle inequality from 4/3 to 2.
引用
收藏
页码：245 / 252
页数：8
相关论文
共 50 条
  • [21] The approximation ratio of the greedy algorithm for the metric traveling salesman problem
    Brecklinghaus, Judith
    Hougardy, Stefan
    OPERATIONS RESEARCH LETTERS, 2015, 43 (03) : 259 - 261
  • [22] Solving the clustered traveling salesman problem via traveling salesman problem methods
    Lu, Yongliang
    Hao, Jin-Kao
    Wu, Qinghua
    PEERJ COMPUTER SCIENCE, 2022, 7
  • [23] A Branch & Cut Algorithm for the Asymmetric Traveling Salesman Problem with Precedence Constraints
    Norbert Ascheuer
    Michael Jünger
    Gerhard Reinelt
    Computational Optimization and Applications, 2000, 17 : 61 - 84
  • [24] A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem
    Svensson, Ola
    Tarnawski, Jakub
    Vegh, Laszlo A.
    JOURNAL OF THE ACM, 2020, 67 (06)
  • [25] A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem
    Svensson, Ola
    Tarnawski, Jakub
    Vegh, Laszlo A.
    STOC'18: PROCEEDINGS OF THE 50TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2018, : 204 - 213
  • [26] A branch & cut algorithm for the asymmetric traveling salesman problem with precedence constraints
    Ascheuer, N
    Jünger, M
    Reinelt, G
    COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2000, 17 (01) : 61 - 84
  • [27] Genetic algorithm for asymmetric traveling salesman problem with imprecise travel times
    Majumdar, J.
    Bhunia, A. K.
    JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, 2011, 235 (09) : 3063 - 3078
  • [28] An O(log n/log log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem
    Asadpour, Arash
    Goemans, Michel X.
    Madry, Aleksander
    Gharan, Shayan Oveis
    Saberi, Amin
    OPERATIONS RESEARCH, 2017, 65 (04) : 1043 - 1061
  • [29] Neighborhood reduction strategy for tabu search implementation in asymmetric traveling salesman problem
    Basu, Sumanta
    OPSEARCH, 2012, 49 (04) : 400 - 412
  • [30] The Pheromone-Based Harmony Search Algorithm for the Asymmetric Traveling Salesman Problem
    Szwarc, Krzysztof
    Boryczka, Urszula
    APPLIED SCIENCES-BASEL, 2020, 10 (18):
12345