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 条

[1]

[Anonymous], 1971, STOC 71, DOI DOI 10.1145/800157.805047

[2]

Busacker R.G., 1965, FINITE GRAPHS NETWOR

[3]

CHRISTOFIDES N, 1976, 388 CARN MELL U MAN

[4]

EDMONDS J, 1965, OPER RES, VS 13, pB73

[5]

Edmonds J, 1973, MATHEMATICAL PROGRAM, V5, P88

[6] ALGORITHM-97 - SHORTEST PATH [J].

FLOYD, RW .

COMMUNICATIONS OF THE ACM, 1962, 5 (06) :345-345

[7]

Ford Lester R., 1962, FLOWS NETWORKS

[8] APPROXIMATION ALGORITHMS FOR SOME ROUTING PROBLEMS [J].

FREDERICKSON, GN ;

HECHT, MS ;

KIM, CE .

SIAM JOURNAL ON COMPUTING, 1978, 7 (02) :178-193

[9]

GABOW H, 1975, TRCUCS07575 U COL DE

[10]

GAREY MR, 1976, ALGORITHMS COMPLEXIT

← 1 2 →