Abstract
An m-layer three-index assignment problem is considered which is a modification of the classical planar three-index assignment problem. This problem is NP-hard for m ⩾ 2. An approximate algorithm, solving this problem for 1 < m < n/2, is suggested. The bounds on its quality are proved in the case when the input data (the elements of an m × n × n matrix) are independent identically distributed random variables whose values lie in the interval [a n, b n], where b n > a n > 0. The time complexity of the algorithm is O(mn 2 + m 7/2). It is shown that in the case of a uniform distribution (and also a distribution of minorized type) the algorithm is asymptotically exact if m = Θ(n 1 − θ ) and b n/a n = o(n θ) for every constant θ, 0 < θ < 1.

This publication has 13 references indexed in Scilit: