scientific article; zbMATH DE number 3982944
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.
- Strong linear independence in bottleneck algebra
- A note on a new variant of Murty's ranking assignments algorithm
- Trapezoidal matrices and the bottleneck assignment problem
- The dominance assignment problem
- An algorithm for ranking assignments using reoptimization
- scientific article; zbMATH DE number 4081306 (Why is no real title available?)
- scientific article; zbMATH DE number 1900918 (Why is no real title available?)
- scientific article; zbMATH DE number 2118621 (Why is no real title available?)
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)