No label defined (Q3748087)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3982944
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3982944 |
Statements
1986
0 references
algebraic assignment problem
0 references
0.8280977010726929
0 references
0.8031821846961975
0 references
0.8027615547180176
0 references
0.7958692908287048
0 references
0.7904366850852966
0 references
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.
0 references