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 条
  • [41] The Harmony Search algorithm with additional improvement of harmony memory for Asymmetric Traveling Salesman Problem
    Boryczka, Urszula
    Szwarc, Krzysztof
    EXPERT SYSTEMS WITH APPLICATIONS, 2019, 122 : 43 - 53
  • [42] An Ant Colony Optimization and Bayesian Network Structure Application for the Asymmetric Traveling Salesman Problem
    Chen, Nai-Hua
    INTELLIGENT INFORMATION AND DATABASE SYSTEMS (ACIIDS 2012), PT III, 2012, 7198 : 74 - 78
  • [43] Harmony Search Algorithm with Dynamic Adjustment of PAR Values for Asymmetric Traveling Salesman Problem
    Szwarc, Krzysztof
    Boryczka, Urszula
    INTELLIGENT INFORMATION AND DATABASE SYSTEMS (ACIIDS 2020), PT I, 2020, 12033 : 226 - 238
  • [44] Probabilistic Bounds on the k-Traveling Salesman Problem and the Traveling Repairman Problem
    Blanchard, Moise
    Jacquillat, Alexandre
    Jaillet, Patrick
    MATHEMATICS OF OPERATIONS RESEARCH, 2023, 49 (02) : 1169 - 1191
  • [45] The effect of the asymmetry of road transportation networks on the traveling salesman problem
    Rodriguez, Alejandro
    Ruiz, Ruben
    COMPUTERS & OPERATIONS RESEARCH, 2012, 39 (07) : 1566 - 1576
  • [46] A survey on the Traveling Salesman Problem and its variants in a warehousing context
    Bock, Stefan
    Bomsdorf, Stefan
    Boysen, Nils
    Schneider, Michael
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2025, 322 (01) : 1 - 14
  • [47] A hybrid approach combining an improved genetic algorithm and optimization strategies for the asymmetric traveling salesman problem
    Xing, Ling-Ning
    Chen, Ying-Wu
    Yang, Ke-Wei
    Hou, Feng
    Shen, Xue-Shi
    Cai, Huai-Ping
    ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE, 2008, 21 (08) : 1370 - 1380
  • [48] New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints
    Sarin, SC
    Sherali, HD
    Bhootra, A
    OPERATIONS RESEARCH LETTERS, 2005, 33 (01) : 62 - 70
  • [49] A model induced max-min ant colony optimization for asymmetric traveling salesman problem
    Bai, Jie
    Yang, Gen-Ke
    Chen, Yu-Wang
    Hu, Li-Sheng
    Pan, Chang-Chun
    APPLIED SOFT COMPUTING, 2013, 13 (03) : 1365 - 1375
  • [50] THE PRECEDENCE-CONSTRAINED ASYMMETRIC TRAVELING SALESMAN POLYTOPE
    BALAS, E
    FISCHETTI, M
    PULLEYBLANK, WR
    MATHEMATICAL PROGRAMMING, 1995, 68 (03) : 241 - 265
12345