Solution methods and computational investigations for the linear bottleneck assignment problem

The Linear Bottleneck Assignment Problem LEAP is analyzed from a computational point of view. Beside a brief review of known algorithms new methods are developed using only sparse subgraphs for their computation. The practical behaviour of both types of algorithms is investigated. The most promising algorithm consists of computing a maximum cardinality matching with all edge costs smaller than a previously determined bound and augmenting this matching to an assignment. The methods on sparse subgraphs are useful in the case of memory restrictions and are superior if the subgraph selection can be improved by some previously generated structure. Other treated questions are how to select a suitable subgraph for the new methods, how to deal with non regular data and what connections to asymptotic results for the LEAP can be detected.