On Approximation Methods for the Assignment Problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On Approximation Methods for the Assignment Problem

Full text

Pdf (1.10 MB)

Source

Journal of the ACM (JACM) archive
Volume 9 , Issue 4 (October 1962) table of contents

Pages: 419 - 439

Year of Publication: 1962

ISSN:0004-5411

Author

Jerome M. Kurtzberg

Burroughs Corporation, Paoli, Pennsylvania

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 35, Citation Count: 9

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/321138.321140 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	CHURCHMAN; AC~OFF; AND ARNOFF. Introduction to Operations Research. John Wiley, New York, 1957. Ch. 12, pp. 343-368.
	2	CRAMER, H. Mathematical Methods of Statistics. Princeton University Press, 1951.
	3	DANTZIG, G. The dual simplex algorithm. RAND Report RM-1270, RAND Corp., Santa Moniea, Calif., 1954.
	4	FELLER, W. ProSab~lity Theory and Its Applications. John Wiley, New York, 1950.
	5	FORD, L.; AND FULKERSON, D. Solving the transportation problem. RAND Report RM-1736, RAND Corp., Santa Monica, Calif., 1956.
	6	GAss, S. Linear Programming. McGraw-Hill, New York, 1958.
	7	GERSTENHABER, M:. A solutmn method for the transportation problem. J. SIAM 6 (1958), 321-334.
	8	KUHN, H.W. Hungarian method for the assignment problem. Nay. Res. Logist. Quart. 2 (1955), 83-97.
	9	KUHN, H. W. Variants of Hungarian method for assignment problems. Nay. Res. Log~st. Quart. 3 (1956), 253-258.
	10	MOTZKIN, T.S. The assignment problem. Proc. 6th Symp. A ppl. Math. VI, pp. 109- 125, McGraw-Hill, New York, 1956.
	11	MUNKRES, J. Algorithms for the assignment and transportation problems. J. SlAM 5 (1957), 32-38.
	12	VON NEUMANN, J. A certain-zero-sum two-person game equivalent to the optimal assignment problem. In H. Kuhn and A. Tucker (eds.), Contribution to the Theory of Games II (Ann. Math. Study No. 28), pp. 5-12, Princeton University Press, 1953.

CITED BY 9

	B. A. Carpenter , N. J. Davis, IV, Implementation and performance analysis of parallel assignment algorithms on a hypercube computer, Proceedings of the third conference on Hypercube concurrent computers and applications, p.1231-1235, January 1989, Pasadena, California, United States
	Tomaso Pomentale, An algorithm for minimizing backboard wiring functions, Communications of the ACM, v.8 n.11, p.699-703, Nov. 1965
	Robert W. Kadis , Kenneth L. Thompson , William J. Volkman, Jr. , W. Lawrence Hill , Charlotte E. Gillette, Building block programs for the layout of printed circuit boards utilizing integrated circuit packs (DAPSYS V.2), Proceedings of the 5th annual workshop on Design automation, p.5.1-5.16, July 15-18, 1968, Washington, D. C., United States
	George S. Lueker, Maximization problems on graphs with edge weights chosen from a normal distribution (Extended Abstract), Proceedings of the tenth annual ACM symposium on Theory of computing, p.13-18, May 01-03, 1978, San Diego, California, United States
	Valerie K. Smith , Robert J. Smith, II , Phil A. Preston, Comet - a fast component placer, Proceedings of the 17th conference on Design automation, p.465-471, June 23-25, 1980, Minneapolis, Minnesota, United States
	Melvin A Breuer, The application of integer programming in design automation, Proceedings of the SHARE design automation project, p.2.1-2.19, January 1966
	Douglas C. Schmidt , Lawrence E. Druffel, An iterative algorithm for placement and assignment of integrated circuits, Proceedings of the 12th conference on Design automation, p.361-368, January 1975
	Mike Pluimer, An approach to ECL module placement, ACM SIGDA Newsletter, v.9 n.1, p.5-8, March 1979
	W. E. Donath, Algorithm and average-value bounds for assignment problems, IBM Journal of Research and Development, v.13 n.4, p.380-386, July 1969