APPROXIMATION ALGORITHMS FOR SOME POSTMAN PROBLEMS

被引：118

作者：

FREDERICKSON, GN ^{[1
]}

机构：

[1] UNIV MARYLAND,COLLEGE PK,MD 20742

来源：

JOURNAL OF THE ACM | 1979年 / 26卷 / 03期

关键词：

Chinese postman problem; heuristic; mixed postman problem; mixed strategy; NPcomplete; polynomial-time approximation algorithm; problems; rural postman problem; worst-case performance bound;

D O I：

10.1145/322139.322150

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

Approxtmatton algorithms for several NP-complete edge-covermg routing problems are presented and analyzed m terms of the worst-case ratio of the cost of the obtained solutmn to the cost of the optimum solutton A worst-case bound of 2 is proved for the mixed postman algortthm of Edmonds and Johnson, and a related algorithm for the mixed postman problem is shown also to have a worst-case bound of 2 A mixed strategy approach ts used to obtain a bound of is for the mixed postman problem A second mixed strategy algorithm, for the mtxed postman on a planar graph, is shown to have a worst-case bound of. © 1979, ACM. All rights reserved.

引用

页码：538 / 554

页数：17

共 20 条

[11] APPROXIMATION ALGORITHMS FOR COMBINATORIAL PROBLEMS [J].

JOHNSON, DS .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1974, 9 (03) :256-278

[12]

Karp Richard M., 1972, COMPLEXITY COMPUTER, P85

[13]

Lawler EL., 2001, COMBINATORIAL OPTIMI

[14]

Lenstra J. K., 1976, Networks, V6, P273, DOI 10.1002/net.3230060305

[15]

MEIKO K, 1962, CHINESE MATH, V1, P237

[16]

Orloff C. S., 1976, Networks, V6, P281, DOI 10.1002/net.3230060306

[17]

Orloff C. S, 1974, NETWORKS, V4, P35, DOI [10.1002/net.3230040105, DOI 10.1002/NET.3230040105]

[18] COMPLEXITY OF EDGE TRAVERSING [J].

PAPADIMITRIOU, CH .

JOURNAL OF THE ACM, 1976, 23 (03) :544-554

[19]

ROSENKRANTZ DJ, 1977, SIAM J COMPTNG, V6, P115

[20] APPROXIMATE ALGORITHMS FOR 0/1 KNAPSACK PROBLEM [J].

SAHNI, S .

JOURNAL OF THE ACM, 1975, 22 (01) :115-124

← 1 2 →