A computational analysis of the Auction Algorithm

The so-called linear assignment problem (LAP) is a special case of linear programming and one of the important early applications. Because of its structure, the LAP has always been easier to solve than the general LP, and over decades various specific algorithms have been developed. The most recent is one called the Auction Algorithm, which has proved empirically to be highly efficient. This paper undertakes to explain this fine performance by providing an analysis of the computational complexity of the auction algorithm. Underlying assumptions are necessary about the statistical distribution of the ensemble of coefficient sets of the LAP, so the result is an expected value, O(N² log N). Some theoretical approximations are used; and to maintain a degree of rigor, error budgets are applied to these approximations.