Том 13, серия 2, номер 1, 2006 г., Стр. 10-26

УДК 519.8
Э. Х. Гимади, Ю. В. Глазков
Об асимптотически точном алгоритме решения одной модификации трёхиндексной планарной задачи о назначениях

Аннотация:
Рассматривается $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.

Гимади Э. Х. ¹
Глазков Ю. В. ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

Статья поступила 16 ноября 2005 г.