Том 20, номер 5, 2013 г., Стр. 66-83

УДК 519.8
Цидулко О. Ю.
О разрешимости 8-индексной аксиальной задачи о назначениях на одноциклических подстановках

Аннотация:
Рассматривается 8-индексная аксиальная задача о назначениях на одноциклических подстановках. Для этой комбинаторной задачи долгое время оставался открытым вопрос о совместности её системы ограничений для одноциклических подстановок длины n. Доказано, что эта система совместна при нечётных n ≥ 87.
Ил. 4, библиогр. 11.

Ключевые слова: многоиндексная задача о назначениях, аксиальность, разрешимость, одноциклическая подстановка.

Цидулко Оксана Юрьевна ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: tsidulko.ox@gmail.com

Статья поступила 15 февраля 2012 г.
Исправленный вариант — 2 мая 2013 г.

Литература

[1] Гимади Э. Х., Ивонина Е. В. Приближённые алгоритмы решения задачи о двух коммивояжёрах на максимум // Дискрет. анализ и исслед. операций. - 2012. - Т. 19, № 1. - C. 17–32.

[2] Гимади Э. Х., Коркишко Н. М., Сердюков А. И. О разрешимости многоиндексной аксиальной задачи о назначениях на одноциклических подстановках // Изв. вузов. Математика. - 2000. - № 12. - С. 21–26.

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

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

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

[6] Гимади Э. Х., Сердюков А. И. Аксиальные задачи о назначении и коммивояжёра: быстрые приближённые алгоритмы и их вероятностный анализ // Изв. вузов. Математика. - 1999. - Т. 451, №12. - С. 19–25.

[7] Коркишко Н. М. Приближенные алгоритмы решения некоторых многоиндексных задач о назначениях: Дис. . . . канд. физ.-мат. наук: 01.01.09. - Новосибирск, 2003. - 116 c.

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

[9] 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.

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

[11] 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.