An asymptotically exact algorithm for one modification of planar three-index assignment

E. Kh. Gimadi ; Yu. V. Glazkov

Diskretnyj analiz i issledovanie operacij, Tome 13 (2006) no. 1, pp. 10-26

Résumé

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\geqslant2$. An approximate algorithm, solving this problem for $1$, is suggested. The bounds on its quality are proved in the case when the input data (the elements of an $m\times n\times 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=\Theta(n^{1-\theta})$ and $b_n/a_n=o(n^\theta)$ for every constant $\theta$, $0\theta1$.