On the integrality ratio for the asymmetric traveling salesman problem

• 成果类型: Article
• 署名作者: Charikar, Moses; Goemans, Michel X.; Karloff, Howard
• 署名单位: Princeton University; Massachusetts Institute of Technology (MIT); AT&T
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1060.0191
• 发表日期: 2006
• 页码: 245-252
• 关键词: tsp

摘要

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.