Algorithms for capacitated vehicle routing

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Algorithms for capacitated vehicle routing

Full text

Pdf (1.31 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirtieth annual ACM symposium on Theory of computing table of contents

Dallas, Texas, United States

Pages: 349 - 358

Year of Publication: 1998

ISBN:0-89791-962-9

Authors

Moses Charikar	Department of Computer Science, Stanford University
Samir Khuller	Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland, College Park
Balaji Raghavachari	Department of Computer Science, University of Texas, Dallas

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 38, Citation Count: 1

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/276698.276786 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	S. Anily and J. Bramel, "~pproximation algorithms for the capacitated traveling salesman problem with pick-ups and deliveries;' Manuscript, (1997).
	2	S. Anily and R. Hassin, "The swapping problem" Networks, 22:419-433, (1992).
	3	E. Arkin, R. Hassin and L. Klein, "Restricted delivery problems on a network" lgenvorks, 29:205-216, (1997).
	4	S. Arora, Polynomial time approximation schemes for Euclidean TSP and other geometric problems, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.2, October 14-16, 1996
	5	S. Arora, Nearly linear time approximation schemes for Euclidean TSP and other geometric problems, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.554, October 19-22, 1997
	6	Tetsuo Asano , Naoki Katoh , Hisao Tamaki , Takeshi Tokuyama, Covering points in the plane by k-tours: towards a polynomial time approximation scheme for general k, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.275-283, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258602]
	7	Mikhail J. Atallah , S. Rao Kosaraju, Efficient solutions to some transportation problems with applications to minimizing robot arm travel, SIAM Journal on Computing, v.17 n.5, p.849-869, October 1988 [doi>10.1137/0217053]
	8	John Adrian Bondy, Graph Theory With Applications, Elsevier Science Ltd, 1976
	9	D.O. Casco, B. L. Golden and E. A. Wasil, "Vehicle routing with backhauls: models, algorithms and case studies" Vehicle Routing: Methods and Studies, Eds: Golden and ,~sad, North Holland, Amsterdam (1988).
	10	P. Chalasani, R. Motwani and A. Rao, "Algorithms for robot grasp and delivery" 2nd international Ilbr'kshop on Algoritbanic Foundations of Robotics, (1996).
	11	N. Christofides, "Vehicle routing;' in The traveling salesman problem, edited by E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan and D. B. Shmoys, John Wiley & Sons, New York, Pages 431-448, (1985).
	12	Greg N. Frederickson, A note on the complexity of a simple transportation problem, SIAM Journal on Computing, v.22 n.1, p.57-61, Feb. 1993 [doi>10.1137/0222005]
	13	Greg N. Frederickson , D. J. Guan, Nonpreemptive ensemble motion planning on a tree, Journal of Algorithms, v.15 n.1, p.29-60, July 1993 [doi>10.1006/jagm.1993.1029]
	14	Greg N. Frederickson , D. J. Guan, Preemptive ensemble motion planning on a tree, SIAM Journal on Computing, v.21 n.6, p.1130-1152, Dec. 1992 [doi>10.1137/0221066]
	15	G. N. Frederiekson, M. S. Hecht and C. E. Kim, "Approximation algorithms for some routing problems;' SIAM J. Comput., 7(2):178-193, (1978).
	16	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	17	M. Haimovich and A. H. G. Rinnooy Kan, "Bounds and heuristics for capaeitated routing problems;' Math. Oper. Res. 10:527-542, (1985).
	18	R. M. Karp, "Two combinatorial problems associated with external sorting" Combinatorial Algorithnts, Cottrant Comp. $ci. Syrup., Pages 17-29, Algorithmics Press, New York, (1972).
	19	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	20	Joseph S. B. Mitchell, Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems, SIAM Journal on Computing, v.28 n.4, p.1298-1309, Aug. 1999 [doi>10.1137/S0097539796309764]