The Hungarian method for the assignment problem

Wiley - Tập 2 Số 1-2 - Trang 83-97 - 1955
Harold W. Kuhn1
1Bryn Mawr College

Tóm tắt

Abstract

Assuming that numerical scores are available for the performance of each of n persons on each of n jobs, the “assignment problem” is the quest for an assignment of persons to jobs so that the sum of the n scores so obtained is as large as possible. It is shown that ideas latent in the work of two Hungarian mathematicians may be exploited to yield a new method of solving this problem.

Từ khóa


Tài liệu tham khảo

10.1007/BF01456961

Frobenius G. “Über zerlegbare Determinanten ” Sitzungsber. Preuss. Akad. Wiss. (1917)274–277.

Egerváry J. “Matrixok kombinatorius tulájdonsigairól.” Mat. Fiz. Lapok (1931)16–28(translated as “Combinatorial Properties of Matrices” by H. W. Kuhn ONR Logistics Project Princeton (1953) mimeographed).

10.1112/jlms/s1-10.37.26

10.1112/jlms/s1-21.3.219

Birkhoff Garrett, 1946, Tres Observaciones sobre el Algebra Lineal, Univ. Nac. Tucumán. Revista, 5, 147

10.1007/BF02289039

Dantzig G. B. “Application of the Simplex Method to a Transportation Problem ”Chapter XXIII in Activity Analysis of Production and Allocation Cowles Commission Monograph No.13 ed. T. C. Koopmans New York 1951.

Votaw D. F., 1952, The Personnel Assignment Problem, Symposium on Linear Inequalities and Programming, SCOOP, 10, 155

von Neumann J., 1953, A Certain Zero‐sum Two‐Pereon Game Equivalent to the Optimal Assignment Problem, Contributions to the Theory of Games II, Ann. Math. Study, 28, 5

10.1007/BF02288990

10.2140/pjm.1953.3.369

Motzkin T. S., The Assignment Problem, Proc. of Sixth Symposium on Applied Mathematics