On a new variant of Murty's ranking assignments algorithm

Authors

Abstract

In this paper a variant of Murty's algorithm for ranking assignments according to its cost is presented.
It is shown that the worst-case computational complexity is better in this variant than in the original form of the algorithm.
Finally, some computational results are presented, allowing the conclusion that the behaviour of the new variant is also better in practice.

Keywords

Graph Theory, Mathematical Programming, Combinatorics

Journal

4OR -- Quarterly Journal of the Belgian, French and Italian Operations Research Societies, Vol. 1, #3, pp. 243-256, September 2003