Об асимптотически точном алгоритме решения одной модификации трёхиндексной планарной задачи о назначениях

Рассматривается $m$-слойная трёхиндексная планарная задача о назначениях, являющаяся модификацией классической трёхиндексной планарной задачи о назначениях. Эта задача NP-трудна при $m\geqslant2$. Предложен приближённый алгоритм решения задачи при $1<m<n/2$. Установлены оценки качества его работы в случае, когда входные данные (элементы матрицы размера $m\times n\times n$) являются независимыми одинаково распределёнными случайными величинами со значениями на отрезке $[a_n,b_n]$, где $b_n>a_n>0$. Алгоритм имеет временную сложность $O(mn^2+m^{7/2})$. Показано, что в случае равномерного распределения (а также распределения минорируемого типа) алгоритм является асимптотически точным, если $m=\Theta(n^{1-\theta})$ и $b_n/a_n=o(n^\theta)$ для любой константы $\theta$, $0<\theta<1$.
Библ. 23.