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 条
12345