|
Дискретный анализ и исследование операций, 2014, том 21, выпуск 1, страницы 15–29
(Mi da757)
|
|
|
|
Эта публикация цитируется в 7 научных статьях (всего в 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 с различными весовыми функциями, полиномиальный алгоритм, асимптотическая точность.
Статья поступила: 19.12.2012 Переработанный вариант: 29.03.2013
Образец цитирования:
Э. Х. Гимади, Ю. В. Глазков, О. Ю. Цидулко, “Вероятностный анализ алгоритма решения трёхиндексной $m$-слойной планарной задачи о назначениях на одноциклических подстановках”, Дискретн. анализ и исслед. опер., 21:1 (2014), 15–29; J. Appl. Industr. Math., 8:2 (2014), 208–217
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da757 https://www.mathnet.ru/rus/da/v21/i1/p15
|
Статистика просмотров: |
Страница аннотации: | 498 | PDF полного текста: | 121 | Список литературы: | 48 | Первая страница: | 9 |
|