On the integrality ratio for asymmetric TSP

被引：4

作者：

Charikar, M ^{[1
]}

Goemans, MX ^{[1
]}

Karloff, H ^{[1
]}

机构：

[1] Princeton Univ, Dept Comp Sci, Princeton, NJ 08540 USA

来源：

45TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS | 2004年

关键词：

D O I：

10.1109/FOCS.2004.45

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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.

引用

页码：101 / 107

页数：7