The Computational Efficiency of Ji-Lee-Li Algorithm for the Assignment Problem

Authors

  • Boris Goldengorin University of Groningen
  • Gerold Jäger Institut f¨ur Informatik, Martin-Luther-Universit¨at Halle-Wittenberg

Keywords:

Assignment Problem, Hungarian algorithm, Dual Simplex algorithm

Abstract

Ji et al. have conjectured that using the matrix form (to represent a basic solution) instead of the Simplex tableau in the dual Simplex method will lead to an algorithm with the time complexity comparable to the Hungarian algorithm for solving the Assignment Problem. In this note we show that both the time complexity and the CPU times of the Ji et al. algorithm are far away from being competitive to the Hungarian algorithm.

Author Biographies

Boris Goldengorin, University of Groningen

Econometrics and Operations Research Dept., associate professor

Gerold Jäger, Institut f¨ur Informatik, Martin-Luther-Universit¨at Halle-Wittenberg

Computer Science Institute, Post-doc

Downloads

Published

2008-03-25

How to Cite

Goldengorin, B., & Jäger, G. (2008). The Computational Efficiency of Ji-Lee-Li Algorithm for the Assignment Problem. Algorithmic Operations Research, 3(1). Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/1240

Issue

Vol. 3 No. 1 (2008)

Section

Short Communications

License

The copyright of the submitted article is hereby transferred to “Preeminent Academic Facets Inc. (the “publisher”) to the extent possible by the laws in the respective countries of the author(s). The author(s) retain all other rights including the following: 1. Any patents and trademark rights. 2. Right to post a pre-print version of the paper on the author’s personal website which is not used for commercial purposes. The author(s) warrant that the work is original, it has not been published elsewhere, it is not currently under consideration for publication in any form, and it does not infringe any copyright laws. The signing author or agent further warrants that all authors, if applicable, have been informed of the terms of this agreement and obtained the approval and authority to sign the agreement.