EN|RU

Том 18, номер 3, 2011 г., Стр. 11-20

УДК 519.8
Гимади Э. Х., Дементьев В. Т.
Вероятностный анализ децентрализованной версии одного обобщения задачи о назначениях

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

Ключевые слова: децентрализованная транспортная задача, NP-трудность, приближённый алгоритм, асимптотическая точность, теорема Петрова, равномерное распределение.

Гимади Эдуард Хайрутдинович 1,2
Дементьев Владимир Тихонович 1,2

1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: gimadi@math.nsc.ru, dementev@math.nsc.ru

Статья поступила 11 марта 2010 г.
Исправленный вариант — 12 апреля 2011 г.

 © Институт математики им. С. Л. Соболева, 2015