Полиномиальный 3/5-приближённый алгоритм для несимметричной задачи о трёх коммивояжёрах на максимум | Sciact - Система учета научной деятельности ИМ СО РАН

Полиномиальный 3/5-приближённый алгоритм для несимметричной задачи о трёх коммивояжёрах на максимум Научная публикация

Журнал

Дискретный анализ и исследование операций
ISSN: 1560-7542

Вых. Данные

Год: 2019, Том: 26, Номер: 2, Страницы: 30-59 Страниц : 30

Ключевые слова

гамильтонов цикл; задача коммивояжёра; задача нескольких коммивояжёров; приближённый алгоритм; гарантированная оценка точности

Авторы

Глебов А.Н. ^1,2 , Токтохоева С.Г. ²

Организации

1	1Институт математики им. С. Л. Соболева
2	Новосибирский государственный университет

Разработан первый полиномиальный приближённый алгоритм с гарантированной оценкой точности для несимметричного случая задачи о трёх коммивояжёрах на максимум, где требуется найти три рёберно непересекающихся гамильтоновых цикла максимального суммарного веса в полном взвешенном ориентированном графе. Для полученного алгоритма обоснована гарантированная оценка точности 3/5 и кубическая оценка временной сложности. © А. Н. Глебов, С. Г. Токтохоева, 2019

Глебов А.Н. , Токтохоева С.Г.
Полиномиальный 3/5-приближённый алгоритм для несимметричной задачи о трёх коммивояжёрах на максимум
Дискретный анализ и исследование операций. 2019. Т.26. №2. С.30-59.

Glebov A.N. , Toktokhoeva S.G.
A Polynomial 3/5-Approximate Algorithm for the Asymmetric Maximization Version of the 3-PSP
Journal of Applied and Industrial Mathematics. 2019. V.13. N2. P.219-238. DOI: 10.1134/S1990478919020042 Scopus OpenAlex

Поступила в редакцию:	6 июн. 2018 г.
Принята к публикации:	28 нояб. 2018 г.

Нет идентификаторов

Пока нет цитирований