Том 21, номер 1, 2014 г., Стр. 15–29

УДК 519.8
Э. Х. Гимади, Ю. В. Глазков, О. Ю. Цидулко
Вероятностный анализ алгоритма решения трёхиндексной m-слойной планарной задачи о назначениях на одноциклических подстановках

Аннотация:
Рассматривается трёхиндексная планарная m-слойная задача о назначениях на одноциклических подстановках, являющаяся в общем случае задачей m коммивояжёров с различными весовыми функциями их маршрутов. Задача NP-трудна при m > 1. Представлен приближённый полиномиальный алгоритм решения задачи при 1 < m < n/4. Алгоритм имеет временную сложность O(mn²). Получены оценки качества его работы в случае, когда входные данные (элементы (m×n×n)-матрицы) являются независимыми случайными величинами с общей функцией равномерного распределения на отрезке [a_n, b_n], где 0 < a_n < b_n. Получены условия асимптотической точности алгоритма, верные также в случае функции распределения мажорирующего типа.
Ил. 1, библиогр. 26.

Ключевые слова: трёхиндексная планарная задача о назначениях, m-слойная задача на одноциклических подстановках, m-PSP с различными весовыми функциями,  полиномиальный алгоритм, асимптотическая точность.

Гимади Эдуард Хайрутдинович ^1,2
Глазков Юрий Владимирович ¹
Цидулко Оксана Юрьевна ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: gimadi@math.nsc.ru, yg@ngs.ru, tsidulko.ox@gmail.com 

Статья поступила 19 декабря 2012 г.
Исправленный вариант — 29 марта 2013 г.

Литература

[1] Бабурин А. Е., Гимади Э. Х. Об асимптотической точности эффективного алгоритма решения задачи m-PSP на максимум в многомерном евклидовом пространстве // Тр. ИММ УрО РАН. - 2010. - Т. 16, № 3. - С. 12–24.
Baburin A. E., Gimadi E. Kh. On the asymptotic optimality of an algorithm for solving the maximum m-PSP in a multidimensional Euclidean space // Proc. Steklov Inst. Math. - 2011. - Vol. 272, N 1 Suppl. - P. 1–13.

[2] Вознюк И. П., Гимади Э. Х., Филатов М. Ю. Асимптотически точный алгоритм для решения задачи размещения с ограниченными объёмами производства // Дискрет. анализ и исслед. операций.
Сер. 2. - 2001. - Т. 8, № 2. - С. 3–16.

[3] Гимади Э. Х. Асимптотически точный подход к решению многоиндексной аксиальной задачи о назначении // Тр. XI Междунар. Байкальской школы-семинара. Пленарные доклады. - Иркутск: Изд. СЭИ СО РАН, 1998. - С. 62–65.

[4] Гимади Э. Х., Глазков Ю. В. Об асимптотически точном алгоритме решения одной модификации планарной трёхиндексной задачи о назначениях // Дискрет. анализ и исслед. операций. Сер. 2. - 2006. - Т. 13, № 1. - С. 10–26.
Gimadi E. Kh., Glazkov Yu. V. An asymptotically exact algorithm for one modification of planar three-index assignment problem // J. Appl. Industr. Math. - 2007. - Vol. 1, N 4. - P. 442–452.

[5] Гимади Э. Х., Коркишко Н. М. Об одном алгоритме решения трёхиндексной аксиальной задачи о назначениях на одноциклических подстановках // Дискрет. анализ и исслед. операций. Сер. 1. - 2003. - Т. 10, № 2. - С. 35–45.

[6] Гимади Э. Х., Ивонина Е. В. Приближённые алгоритмы решения задачи о двух коммивояжёрах на максимум // Дискрет. анализ и исслед. операций. - 2012. - Т. 19, № 1. - C. 17–32.
Gimadi E. Kh., Ivonina E. V. Approximation algorithms for the maximum 2-peripatetic salesman problem // J. Appl. Industr. Math. - 2012. - Vol. 6, N 3. - P. 295–305.

[7] Глебов А. Н., Гордеева А. В., Замбалаева Д. Ж. Алгоритм с оценкой 7/5 для задачи о двух коммивояжёрах на минимум с различными весовыми функциями // Сиб. электрон. мат. изв. - 2011. - T. 8. - C. 296–309.

[8] Глебов А. Н., Замбалаева Д. Ж. Полиномиальный алгоритм с оценкой точности 7/9 для задачи о двух коммивояжёрах на максимум // Дискрет. анализ и исслед. операций. - 2011. - Т. 18, № 4. - С. 17–48.
Glebov A. N., Zambalaeva D. Zh. A polynomial algorithm with approximation ratio 7/9 for the maximum two peripatetic salesmen problem // J. Appl. Industr. Math. - 2012. - Vol. 6, N 3. - P. 69–89.

[9] Глебов А. Н., Замбалаева Д. Ж. Приближённый алгоритм решения задачи о двух коммивояжёрах на минимум с различными весовыми функциями // Дискрет. анализ и исслед. операций. - 2011. - Т. 18, № 5. - С. 11–37.

[10] Диниц Е. А., Кронрод М. А. Один алгоритм решения задачи о назначениях // Докл. АН СССР.- 1969. - Т. 189, № 1. - C. 23–25.

[11] Емеличев В. А., Ковалев М. М., Кравцов М. М. Многогранники, графы, оптимизация. - М: Наука, 1981. - 342 c.

[12] Кравцов М. К., Крачковский А. П. О полиномиальном алгоритме нахождения асимптотически оптимального решения трёхиндексной планарной проблемы выбора // Журн. вычисл. математики и мат. физики. - 2001. - Т. 41, № 2. - С. 342–345.

[13] Кравцов М. К., Крачковский А. П. Асимптотическая оптимальность плана транспортной задачи, построенного методом минимального элемента // Кибернетика и систем. анализ. - 1999. - № 1. - С. 144–151.

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

[15] Balas E., Saltzman M. J. Facets of the three-index assignment polytope // Discrete Appl. Math. - 1989. - Vol. 23, N 3. - P. 201–229.

[16] Balas E., Saltzman M. J. An algorithm for the three-index assignment problem // Oper. Res. - 1991. - Vol. 39, N 1. - P. 150–161.

[17] Burkard R., Dell’Amico M., Martello S. Assignments. - Philadelphia: SIAM, 2009. - 382 p.

[18] Fon-Der-Flaass D. G. Array of distinct representatives - a very simple NP-complete problem // Discrete Math. - 1997. - Vol. 171, N 1–3. - P. 295–298.

[19] Frieze A. M. Complexity of a 3-dimensional assignment problem // Eur. J. Oper. Res. - 1983. - Vol. 13, N 2. - P. 161–164.

[20] Gimadi E. Kh. On some probability inequalities in some discrete optimization problems // Oper. Res., 2005. Proc. - Berlin: Springer-Verl., 2006. - P. 283–289.

[21] Gimadi E. Kh., Kairan N. M. Multi-index assignment problem: an asymptotically optimal approach // Proc. 8th IEEE Int. Conf. Emerging Technologies and Factory Automation (Antibes - Juan-les-Pins, France, 15–18 October 2001). - Paris: Institute of Electrical and Electronics Engineers, Inc., 2001. - P. 707–710.

[22] Gimadi E. Kh., Korkishko N. M. On some modifications of the three-index planar assignment problem // Discrete optimization methods in production and logistics. 2nd Int.Workshop (Omsk - Irkutsk, July 20–27, 2004). Proc. DOM’2004. - Omsk: Nasledie Dialog-Sibir Pbs., 2004. - P. 161–165.

[23] Krarup J. The peripatetic salesman and some related unsolved problems // Comb. Programming: Methods and Applications (Proc. NATO Adv. Study Inst., Versailles, 1974). - Dordrecht: Reidel, 1975. - P. 173–178.

[24] Magos D. Tabu search for the planar three-index assignment problem // J. Global Optim. - 1996. - Vol. 8, N 1. - P. 35–48.

[25] Spieksma F. C. R. Multi index assignment problems: complexity, approximation, applications // Nonlinear assignment problems, algorithms, and applications. - Dordrecht: Kluwer Acad. Publ., 2000. - P. 1–12.

[26] Vlach M. Branch and bound method for the three-index assignment problem // Ekonomicko-Matematicky Obzor. - 1967. - Vol. 3. - P. 181–191.