- Код статьи
- 10.31857/S0005231024080063-1
- DOI
- 10.31857/S0005231024080063
- Тип публикации
- Статья
- Статус публикации
- Опубликовано
- Авторы
- Том/ Выпуск
- Том / Номер выпуска 8
- Страницы
- 86-98
- Аннотация
- Рассматривается трехиндексная аксиальная задача о назначениях, которая является одной из классических NP-трудных задач. В рамках задачи о назначениях ставится задача комбинирования допустимых решений, представляющая собой задачу о назначениях на множестве решений, которые содержат только компоненты выбранных допустимых решений. Исследуются вопросы комбинирования решений для многокритериальной задачи с различными видами сверток критериев. В общем случае задача комбинирования оказывается NP-трудной. В работе выделяются условия, при которых задача комбинирования полиномиально разрешима.
- Ключевые слова
- аксиальная задача о назначениях многоиндексные задачи комбинирование решений полиномиальная разрешимость NP-трудность
- Дата публикации
- 15.08.2024
- Год выхода
- 2024
- Всего подписок
- 0
- Всего просмотров
- 11
Библиография
- 1. Spieksma F.C.R. Multi Index Assignment Problems. Complexity, Approximation, Applications. P.M. Pardalos, L.S. Pitsoulis (Eds.) / Nonlinear Assignment Problems: Algorithms and Applications. Dordrecht: Kluwer Acad. Publishers, 2000. P. 1-11.
- 2. Burkard R., Dell’Amico M., Martello S. Assignment problems: revised reprint. PA: SIAM, 2012.
- 3. Kuroki Y., Matsui T. An approximation algorithm for multidimensional assignment problems minimizing the sum of squared errors // Discret. Appl. Math. 2009. V. 157. No. 9. P. 2124-2135.
- 4. Poore A.B. Multidimensional Assignment Problems Arising in Multitarget and Multisensor Tracking. P.M. Pardalos, L.S. Pitsoulis (Eds.) / Nonlinear Assignment Problems: Algorithms and Applications. Dordrecht: Kluwer Acad. Publishers, 2000. P. 13-38.
- 5. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
- 6. Crama Y., Spieksma F.C.R. Approximation Algorithms for Three-Dimensional Assignment Problems with Triangle Inequalities // Eur. J. Oper. Res. 1992. V. 60. P. 273-279.
- 7. Bandelt H.J., Crama Y., Spieksma F.C.R. Approximation algorithms for multidimensional assignment problems with decomposable costs // Discret. Appl. Math. 1994. V. 49. P. 25-50.
- 8. Burkard R.E., Rudolf R., Woeginger G.J. Three-dimensional axial assignment problems with decomposable cost coefficients // Discret Appl. Math. 1996. V. 65. P. 123-139.
- 9. Spieksma F., Woeginger G. Geometric three-dimensional assignment problems // Eur. J. Oper. Res. 1996. V. 91. P. 611-618.
- 10. Custic A., Klinz B., Woeginger G.J. Geometric versions of the three-dimensional assignment problem under general norms // Discret. Optim. 2015. V. 18. P. 38-55.
- 11. Balas E., Saltzman M.J. An Algorithm for the Three-Index Assignment Problem // Oper. Res. 1991. V. 39. No. 1. P. 150-161.
- 12. Natu S., Date K., Nagi R. GPU-accelerated Lagrangian heuristic for multidimensional assignment problems with decomposable costs // Parallel Comput. 2020. V. 97. 102666.
- 13. Huang G., Lim A. A hybrid genetic algorithm for the Three-Index Assignment Problem // Eur. J. Oper. Res. 2006. V. 172. P. 249-257.
- 14. Kim B.J., Hightower W.L., Hahn P.M., Zhu Y.R., Sun L. Lower bounds for the axial three-index assignment problem // Eur. J. Oper. 2010. V. 202. P. 654-668.
- 15. Дичковская С.А., Кравцов М.К. Исследование полиномиальных алгоритмов решения трехиндексной планарной проблемы выбора // Журн. вычислит. мат. и мат. физики. 2006. Т. 46. № 2. С. 222-228.
- 16. Дичковская С.А., Кравцов М.К. Исследование полиномиальных алгоритмов решения многокритериальной трехиндексной планарной задачи о назначениях // Журн. вычислит. мат. и мат. физики. 2007. Т. 47. № 6. С. 1077-1086.
- 17. Емеличев В.А., Перепелица В.А. Сложность дискретных многокритериальных задач // Дискретная математика. 1994. Т. 6. Вып. 1. С. 3-33.
- 18. Прилуцкий М.Х. Многокритериальные многоиндексные задачи объемнокалендарного планирования // Известия РАН. Теория и системы управления. 2007. № 1. C. 78-82.
- 19. Прилуцкий М.Х. Многокритериальное распределение однородного ресурса в иерархических системах // АиТ. 1996. № 2. С. 24-29.
- 20. Афраймович Л.Г., Емелин М.Д. Комбинирование решений аксиальной задачи о назначениях // АиТ. 2021. № 8. С. 159-168.
- 21. Афраймович Л.Г., Емелин М.Д. Эвристические стратегии комбинирования решений трехиндексной аксиальной задачи о назначениях // АиТ. 2021. № 10. С. 6-12.
- 22. Afraimovich L.G., Emelin M.D. Complexity of Solutions Combination for the Three-Index Axial Assignment Problem // Mathematics. 2022. V. 10. No. 7. 1062.
