Approximation algorithms for the asymmetric postman problem

被引：0

作者：

Raghavachari, B ^{[1
]}

Veerasamy, J ^{[1
]}

机构：

[1] Univ Texas, Dept Comp Sci, Richardson, TX 75083 USA

来源：

PROCEEDINGS OF THE TENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS | 1999年

关键词：

asymmetric postman problem; windy postman problem; Chinese postman problem; combinatorial optimization; approximation algorithms; linear programming;

D O I：

暂无

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

The asymmetric postman problem is a generalization of the Chinese postman problem in which the edge-traversal costs are asymmetric. The problem is to compute a shortest tour that traverses every edge of a given graph at least once, and it is known to be NP-hard. An approximation algorithm with a performance ratio of 3/2 for the asymmetric postman problem is presented.

引用

页码：734 / 741

页数：8

共 14 条

[1]

BRUCKER P., 1981, LNCS, V100, P354

[2]

CHRISTOFIDES N, 1984, NOTES CONTROL INFORM, V59

[3]

Edmonds J., 1973, Mathematical Programming, V5, P88, DOI 10.1007/BF01580113

[4] ARC ROUTING-PROBLEMS .1. THE CHINESE POSTMAN PROBLEM [J].

EISELT, HA ;

GENDREAU, M ;

LAPORTE, G .

OPERATIONS RESEARCH, 1995, 43 (02) :231-242

[5] APPROXIMATION ALGORITHMS FOR SOME POSTMAN PROBLEMS [J].

FREDERICKSON, GN .

JOURNAL OF THE ACM, 1979, 26 (03) :538-554

[6] A CUTTING PLANE ALGORITHM FOR THE WINDY POSTMAN PROBLEM [J].

GROTSCHEL, M ;

ZAW, W .

MATHEMATICAL PROGRAMMING, 1992, 55 (03) :339-358

[7] ON THE WINDY POSTMAN PROBLEM [J].

GUAN, M .

DISCRETE APPLIED MATHEMATICS, 1984, 9 (01) :41-46

[8] CHINESE POSTMAN PROBLEM FOR MIXED NETWORKS [J].

MINIEKA, E .

MANAGEMENT SCIENCE, 1979, 25 (07) :643-648

[9]

Nemhauser GeorgeL., 1988, Integer Programming and Combinatorial Optimization

[10] COMPLEXITY OF EDGE TRAVERSING [J].

PAPADIMITRIOU, CH .

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

← 1 2 →