Вероятностный анализ децентрализованной версии одного обобщения задачи о назначениях

Рассматривается децентрализованная полуобобщённая задача о назначениях с $m\times n$-матрицей, где $m=kn$, $k$ – натуральное число. Элементы матрицы – неотрицательные числа. В каждом столбце матрицы выбирается $k$ элементов, в каждой строке – один элемент так, чтобы максимизировать сумму выбранных элементов. Предложен приближённый алгоритм решения с временно́й сложностью $O(mn)$. В случае, когда элементы матрицы являются независимыми случайными величинами с общей функцией равномерного распределения, найдены оценки относительной погрешности и вероятности несрабатывания алгоритма, а также обоснована асимптотическая точность алгоритма. Библиогр. 8.