WORST-CASE ANALYSIS OF 2 TRAVELING SALESMAN HEURISTICS

被引：10

作者：

ONG, HL ^{[1
]}

MOORE, JB ^{[1
]}

机构：

[1] UNIV WATERLOO,DEPT MANAGEMENT SCI,WATERLOO N2L 3G1,ONTARIO,CANADA

来源：

OPERATIONS RESEARCH LETTERS | 1984年 / 2卷 / 06期

关键词：

D O I：

10.1016/0167-6377(84)90078-6

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

引用

页码：273 / 277

页数：5

共 12 条

[1]

CHRISTOFIDES N, 1976, 627576 CARN MELL U G

[2] SCHEDULING OF VEHICLES FROM CENTRAL DEPOT TO NUMBER OF DELIVERY POINTS [J].

CLARKE, G ;

WRIGHT, JW .

OPERATIONS RESEARCH, 1964, 12 (04) :568-&

[3] TIGHT BOUNDS FOR CHRISTOFIDES TRAVELING SALESMAN HEURISTIC [J].

CORNUEJOLS, G ;

NEMHAUSER, GL .

MATHEMATICAL PROGRAMMING, 1978, 14 (01) :116-121

[4] ANALYSIS OF APPROXIMATIONS FOR FINDING A MAXIMUM WEIGHT HAMILTONIAN CIRCUIT [J].

FISHER, ML ;

NEMHAUSER, GL ;

WOLSEY, LA .

OPERATIONS RESEARCH, 1979, 27 (04) :799-809

[5]

FRIEZE A, 1978, OPS RES VERFAHREN, V32, P94

[6]

Garey Michael R., 1979, COMPUTERS INTRACTABI

[7]

Golden B. L., 1977, AIIE Transactions, V9, P204, DOI 10.1080/05695557708975144

[8]

Karp R.M., 1972, COMPLEXITY COMPUTER

[9]

Rosenkrantz D. H., 1977, SIAM Journal on Computing, V6, P563, DOI 10.1137/0206041

[10] P-COMPLETE APPROXIMATION PROBLEMS [J].

SAHNI, S ;

GONZALEZ, T .

JOURNAL OF THE ACM, 1976, 23 (03) :555-565

← 1 2 →