Aarhus University Seal / Aarhus Universitets segl

A note on ranking assignments using reoptimization

By Christian Roed Pedersen, Lars Relund Nielsen and Kim Allan Andersen
Working Papers
No. 02, December 2005
We consider the problem of ranking assignments according to cost in the classical linear assignment problem. An algorithm partitioning the set of possible assignments, as suggested by Murty, is presented where, for each partition, the optimal assignment is calculated using a new reoptimization technique. Computational results for the new algorithm are presented.
Format available: PDF (320.5 kb), PostScript (1029.0 kb)