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

共 25 条

[1] MOLECULAR COMPUTATION OF SOLUTIONS TO COMBINATORIAL PROBLEMS [J].

ADLEMAN, LM .

SCIENCE, 1994, 266 (5187) :1021-1024

[2]

[Anonymous], 2002, COMB OPT (SER)

[3]

[Anonymous], 1976, WORST CASE ANAL NEW

[4] Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems [J].

Arora, S .

JOURNAL OF THE ACM, 1998, 45 (05) :753-782

[5]

Bläser M, 2003, SIAM PROC S, P638

[6]

BOYD S, 2004, COMB OPT 2004 C CO20

[7]

BOYD S, 2002, P 9 C INT PROGR COMB, P83

[8] On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems [J].

Carr, R ;

Vempala, S .

MATHEMATICAL PROGRAMMING, 2004, 100 (03) :569-587

[9] Ant system: Optimization by a colony of cooperating agents [J].

Dorigo, M ;

Maniezzo, V ;

Colorni, A .

IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART B-CYBERNETICS, 1996, 26 (01) :29-41

[10] ON THE WORST-CASE PERFORMANCE OF SOME ALGORITHMS FOR THE ASYMMETRIC TRAVELING SALESMAN PROBLEM [J].

FRIEZE, AM ;

GALBIATI, G ;

MAFFIOLI, F .

NETWORKS, 1982, 12 (01) :23-39

← 1 2 3 →