Development of an accelerating hungarian method for assignment problems

Authors

DOI:

https://doi.org/10.15587/1729-4061.2020.209172

Keywords:

Hungarian method, assignment problem, Kőnig theorem, Egerváry Theorem, Kuhn-Munkres algorithm

Abstract

The Hungarian method is a well-known method for solving the assignment problem. This method was developed and published in 1955. It was named the Hungarian method because two theorems from two Hungarian mathematicians were used. In 1957, it was noticed that this algorithm is strongly polynomial and has a complexity of order O(n4) This is the reason why the Hungarian method is also known as the Kuhn-Munkres algorithm. Later on, in 1971 the complexity of the method was improved to order O(n3) A smallest uncovered element is selected to create a single zero at every iteration. This is a weakness and is alleviated by selecting more than one smallest uncovered element thus creating more than one zero at every iteration to come up with what we now call the Accelerating Hungarian (AH) method.

From the numerical illustration of the Hungarian method given in this paper, we require 6 iterations to reach optimality. It can also be shown that selecting a single smallest uncovered element (es) makes the Hungarian method inefficient when creating zeros. From the same numerical illustration of the proposed algorithm (AH) also given in this paper, it can be noted that only one iteration is required to reach optimality and that a total of six zeros are created in one iteration.

Assignment model and the Hungarian method have application in addressing the Weapon Target Assignment (WTA) problem. This is the problem of assigning weapons to targets while considering the maximum probability of kill. The assignment problem is also used in the scheduling problem of physicians and medical staff in the outpatient department of large hospitals with multi-branches. The mathematical modelling of this assignment problem results in complex problems. A hybrid meta-heuristic algorithm SCA–VNS combining a Sine Cosine Algorithm (SCA) and Variable Neighbourhood Search (VNS) based on the Iterated Hungarian algorithm is normally used.

Author Biography

Elias Munapo, School of Economics and Decision Sciences North-West University Mmabatho Unit 5, Mafikeng, South Africa, 2790

PhD, Professor of Operations Research

Department of Statistics and Operations Research

References

  1. Kuhn, H. W. (1955). The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2 (1-2), 83–97. doi: https://doi.org/10.1002/nav.3800020109
  2. Kőnig, D. (1931). Graphok ´es matrixok. Matematikai ´es Fizikai Lapok, 38, 116–119.
  3. Egerváry, J. (1931). Matrixok kombinatorius tulajdons´agair´ol. Matematikai ´es Fizikai Lapok, 38, 16–28.
  4. Munkres, J. (1957). Algorithms for the Assignment and Transportation Problems. Journal of the Society for Industrial and Applied Mathematics, 5 (1), 32–38. doi: https://doi.org/10.1137/0105003
  5. Edmonds, J., Karp, R. M. (1972). Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems. Journal of the ACM (JACM), 19 (2), 248–264. doi: https://doi.org/10.1145/321694.321699
  6. Tomizawa, N. (1971). On some techniques useful for solution of transportation network problems. Networks, 1 (2), 173–194. doi: https://doi.org/10.1002/net.3230010206
  7. Date, K., Nagi, R. (2016). GPU-accelerated Hungarian algorithms for the Linear Assignment Problem. Parallel Computing, 57, 52–72. doi: https://doi.org/10.1016/j.parco.2016.05.012
  8. Kline, A., Ahner, D., Hill, R. (2019). The Weapon-Target Assignment Problem. Computers & Operations Research, 105, 226–236. doi: https://doi.org/10.1016/j.cor.2018.10.015
  9. Rabbani, Q., Khan, A., Quddoos, A. (2019). Modified Hungarian method for unbalanced assignment problem with multiple jobs. Applied Mathematics and Computation, 361, 493–498. doi: https://doi.org/10.1016/j.amc.2019.05.041
  10. Lan, S., Fan, W., Liu, T., Yang, S. (2019). A hybrid SCA–VNS meta-heuristic based on Iterated Hungarian algorithm for physicians and medical staff scheduling problem in outpatient department of large hospitals with multiple branches. Applied Soft Computing, 85, 105813. doi: https://doi.org/10.1016/j.asoc.2019.105813
  11. Öncan, T., Şuvak, Z., Akyüz, M. H., Altınel, İ. K. (2019). Assignment problem with conflicts. Computers & Operations Research, 111, 214–229. doi: https://doi.org/10.1016/j.cor.2019.07.001
  12. Patil, A. H., Mahalle, P. N. (2020). Trends and Challenges in Measuring Performance of Reviewer Paper Assignment. Procedia Computer Science, 171, 709–718. doi: https://doi.org/10.1016/j.procs.2020.04.077
  13. Zhang, R.-Q., Wang, M., Pan, X. (2019). New model of the storage location assignment problem considering demand correlation pattern. Computers & Industrial Engineering, 129, 210–219. doi: https://doi.org/10.1016/j.cie.2019.01.027
  14. Niv, A., MacCaig, M., Sergeev, S. (2020). Optimal assignments with supervisions. Linear Algebra and Its Applications, 595, 72–100. doi: https://doi.org/10.1016/j.laa.2020.02.032

Downloads

Published

2020-08-31

How to Cite

Munapo, E. (2020). Development of an accelerating hungarian method for assignment problems. Eastern-European Journal of Enterprise Technologies, 4(4 (106), 6–13. https://doi.org/10.15587/1729-4061.2020.209172

Issue

Vol. 4 No. 4 (106) (2020): Mathematics and Cybernetics - applied aspects

Section

Mathematics and Cybernetics - applied aspects

License

Copyright (c) 2020 Elias Munapo

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.

A license agreement is a document in which the author warrants that he/she owns all copyright for the work (manuscript, article, etc.).
The authors, signing the License Agreement with TECHNOLOGY CENTER PC, have all rights to the further use of their work, provided that they link to our edition in which the work was published.
According to the terms of the License Agreement, the Publisher TECHNOLOGY CENTER PC does not take away your copyrights and receives permission from the authors to use and dissemination of the publication through the world's scientific resources (own electronic resources, scientometric databases, repositories, libraries, etc.).
In the absence of a signed License Agreement or in the absence of this agreement of identifiers allowing to identify the identity of the author, the editors have no right to work with the manuscript.
It is important to remember that there is another type of agreement between authors and publishers – when copyright is transferred from the authors to the publisher. In this case, the authors lose ownership of their work and may not use it in any way.