scientific article; zbMATH DE number 3982944

From MaRDI portal
Publication:3748087





Several efficient algorithms for solving the algebraic assignment problem (AAP) are known, one of them of computational complexity \(O(n^ 3)\) was described by \textit{R. E. Burkard} and \textit{U. Zimmermann} [Math. Program. Study. 12, 1-8 (1980; Zbl 0435.90108)]. However, in some cases it may be useful to decide whether the solution of AAP is unique and to determine the second cost of assignment, i.e. the minimal cost assignment after excluding all optimal solutions. An \(O(n^ 3)\) algorithm for the first problem was given by \textit{P. Butkovič} and \textit{F. Hevery} [Discrete Appl. Math. 11, 209-222 (1985)]. The algorithm for ranking all permutations described by \textit{K. G. Murty} [Oper. Res. 16, 682-687 (1968; Zbl 0214.187)] solves in particular the same problem by \(O(n^ 4)\) operations and it can be used to solve the second problem too, but it would not be polynomial in general. The aim of the present paper is to describe (1) an \(O(n^ 3)\) algorithm for the first problem which is more appropriate for implementation than that mentioned above and, (2) an \(O(n^ 4)\) algorithm for the second problem.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3748087)