Approximation Algorithms for Some Postman Problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Approximation Algorithms for Some Postman Problems

Full text

Pdf (1.08 MB)

Source

Journal of the ACM (JACM) archive
Volume 26 , Issue 3 (July 1979) table of contents

Pages: 538 - 554

Year of Publication: 1979

ISSN:0004-5411

Author

Greg N. Frederickson

Computer Science Department, The Pennsylvania State University, University Park, PA and University of Maryland, College Park, Maryland

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 72, Citation Count: 6

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/322139.322150 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	BUSACKER, R G, AND SAATY, T L Fmae Graphs and Networks McGraw-Hall, New York, 1965
	2	CHRISTOFIDES, N Worst-case analys~s of a new heuristic for the travehng salesman problem Manage Sc, Res Rep No 388, Carnegie-Mellon U, Pmsburgh, Pa, 1976
	3	Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
	4	EDMONDS, J The Chinese postman problem Oper Res 13, Suppl 1 (1965), B73-B77
	5	EDMONDS, J, AND JOHNSON, E L Matching, Euler tours and the Chmese postman Math Programming 5 (1973), 88-124
	6	Robert W. Floyd, Algorithm 97: Shortest path, Communications of the ACM, v.5 n.6, p.345, June 1962 [doi>10.1145/367766.368168]
	7	FORD, L R, AND FULKERSON, D R Flows m Networks Prmceton U Press, Princeton, N J, 1962
	8	FEDREDERICKSON, G N, HECHT, M S, AND KIM, C E Approx,mation algorithms for some routmg problems Slam J Comptng 7 (1978), 178-193
	9	GABOW, H, AND LAWLER, E L An efficient ~mplementat~on of Edmonds' algorithm for maximum weight matching on graphs TR CU-CS-075-75, Dept Comptr Sct, U of Colorado, Boulder, Colo, 1975
	10	GAREY, M R, AND JOHNSON, D.S. Approxtmatton algorithms for combinatorial problems. An annotated bibhography In Algorithms and Complemty Recent Results and New D:recUons, J.F Traub, Ed, Academic Press, New York, 1976
	11	Oscar H. Ibarra , Chul E. Kim, Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems, Journal of the ACM (JACM), v.22 n.4, p.463-468, Oct. 1975 [doi>10.1145/321906.321909]
	12	JOriNSON, D S Approxlmatton algorithms for combinatorial problems J Comptr. Syst Sc~. 9 (1974), 256- 278
	13	KARP, R M Reductbdtty among combmatorlal problems In Complex:ty of Computer Computanons, R E Miller and J W Thatcher, Eds, Plenum Press, New York, 1972, pp 85-104
	14	LAWLER, E L Combinatorial Opt:mtzat:ons Networks and Matro:ds Holt, Rinehart, and Winston, New York, 1976
	15	LENSTRA, J ,K, AND RINNOOY KAN, A H G On general routing problems Networks 6 (1976), 273-280
	16	MEt-Ko, K Graphtc programming usmg odd or even points Chinese Mathematics I (1962), 237-277
	17	ORLOFF, C S A fundamental problem m vehtcle routing Networks 4 (1974), 35-64
	18	ORLOFF, C S On general routmg problems Comments Networks 6 (1976), 281-284
	19	Christos H. Papadimitriou, On the complexity of edge traversing, Journal of the ACM (JACM), v.23 n.3, p.544-554, July 1976 [doi>10.1145/321958.321974]
	20	ROSENKRANTZ, D J, STEARNS, R E, AND LEWIS, P M An analysts of several heurtstlcs for the travehng salesman problem SIAM J Comptng 6 (1977), 115-124
	21	Sartaj Sahni, Approximate Algorithms for the 0/1 Knapsack Problem, Journal of the ACM (JACM), v.22 n.1, p.115-124, Jan. 1975 [doi>10.1145/321864.321873]

CITED BY 7

	Balaji Raghavachari , Jeyakesavan Veerasamy, Approximation algorithms for the asymmetric postman problem, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.734-741, January 17-19, 1999, Baltimore, Maryland, United States
	Greg N Frederickson , Ravi Janardan, Optimal message routing without complete routing tables, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.88-97, August 11-13, 1986, Calgary, Alberta, Canada
	Enrique Benavent , Angel Corberán , Estefanía Piñana , Isaac Plana , José M. Sanchis, New heuristic algorithms for the windy rural postman problem, Computers and Operations Research, v.32 n.12, p.3111-3128, December 2005
	Esther M. Arkin , Refael Hassin , Asaf Levin, Approximations for minimum and min-max vehicle routing problems, Journal of Algorithms, v.59 n.1, p.1-18, April 2006
	Hong Yan , Gerald L. Thompson, Finding Postal Carrier Walk Paths in Mixed Graphs, Computational Optimization and Applications, v.9 n.3, p.229-247, March 1, 1998
	José Brandão , Richard Eglese, A deterministic tabu search algorithm for the capacitated arc routing problem, Computers and Operations Research, v.35 n.4, p.1112-1126, April, 2008
	Yi Mei , Ke Tang , Xin Yao, A global repair operator for capacitated arc routing problem, IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, v.39 n.3, p.723-734, June 2009