Том 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 г.

Литература

[1] Бабурин А. Е., Гимади Э. Х. Приближённый алгоритм отыскания $d$-однородного регулярного остовного связного подграфа максимального веса в полном графе со случайными весами рёбер // Дискрет. анализ и исслед. операций. Сер. 2. — 2006. — Т. 13, № 2. — С. 3–20.

[2] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М.: Мир, 1982. — 416 c.

[3] Гимади Э. Х., Глебов Н. И., Перепелица В. А. Алгоритмы с оценками для задач дискретной оптимизации // Проблемы кибернетики. — 1975. — Вып. 31. — С. 35–42.

[4] Гимади Э. Х. О вероятностном анализе приближённого алгоритма решения задачи о $p$-медиане // Дискрет. анализ и исслед. операций. — 2010. — Т. 17, № 3. — С. 19–31.

[5] Дейвид Г. Порядковые статистики. — М.: Наука, 1979. — 336 с.

[6] Дементьев В. Т., Пяткин А. В. О децентрализованной транспортной задаче // Дискрет. анализ и исслед. операций. — 2008. — Т. 15, № 3. — С. 22–30.

[7] Петров В. В. Предельные теоремы для сумм независимых случайных величин. — М.: Наука, 1987. — 416 с.

[8] Burkard R., Dell’Amico M., Martello S. Assignment problems. — Philadelphia: SIAM, 2009. — 378 p.