Эта публикация цитируется в
7 статьях
Вероятностный анализ алгоритма решения трёхиндексной $m$-слойной планарной задачи о назначениях на одноциклических подстановках
Э. Х. Гимадиab,
Ю. В. Глазковb,
О. Ю. Цидулкоb a Новосибирский гос. университет, ул. Пирогова, 2,
630090 Новосибирск, Россия
b Институт математики им. С. Л. Соболева СО РАН, пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
Аннотация:
Рассматривается трёхиндексная планарная
$m$-слойная задача о назначениях на одноциклических подстановках, являющаяся в общем случае задачей
$m$ коммивояжёров с различными весовыми функциями их маршрутов. Задача NP-трудна при
$m\ge1$. Представлен приближённый полиномиальный алгоритм решения задачи при
$1<m<n/4$. Алгоритм имеет временну́ю сложность
$O(mn^2)$. Получены оценки качества его работы в случае, когда входные данные (элементы
$(m\times n\times n)$-матрицы) являются независимыми случайными величинами с общей функцией равномерного распределения на отрезке
$[a_n,b_n]$, где
$0<a_n<b_n$. Получены условия асимптотической точности алгоритма, верные также в случае функции распределения мажорирующего типа. Ил. 1, библиогр. 26.
Ключевые слова:
трёхиндексная планарная задача о назначениях,
$m$-слойная задача на одноциклических подстановках,
$m$-PSP с различными весовыми функциями, полиномиальный алгоритм, асимптотическая точность.
УДК:
519.8 Статья поступила: 19.12.2012
Переработанный вариант: 29.03.2013