Реферат: В 2005 г. Капланом и др. был разработан полиномиальный алгоритм с гарантированной оценкой точности 2/3 для несимметричного случая задачи коммивояжёра на максимум. В 2014 г. Глебов, Замбалаева и Скретнева получили алгоритм с такой же оценкой точности и кубической оценкой временной сложности для несимметричного случая задачи о двух коммивояжёрах на максимум, где требуется найти два рёберно не пересекающихся гамильтоновых цикла максимального суммарного веса в полном взвешенном n-вершинном ориентированном графе. Целью настоящей работы является построение аналогичного алгоритма для более общей задачи об m коммивояжёрах на максимум в несимметричном случае и обоснование для этого алгоритма оценки точности, асимптотически стремящейся к 2/3 с ростом m, и оценки временной сложности O(mn^3). Ил. 2, библиогр. 29. © А. Н. Глебов, С. Г. Токтохоева, 2020

Библиографическая ссылка: Глебов А.Н. , Токтохоева С.Г.
Полиномиальный алгоритм с асимптотической оценкой точности 2/3 для несимметричной задачи об m коммивояжёрах на максимум
Дискретный анализ и исследование операций. 2020. Т.27. №3. С.28–52.

Переводная: Glebov A.N. , Toktokhoeva S.G.
A Polynomial Algorithm with Asymptotic Ratio 2/3 for the Asymmetric Maximization Version of the m-PSP
Journal of Applied and Industrial Mathematics. 2020. V.14. N3. P.456-469. DOI: 10.1134/S1990478920030059 Scopus OpenAlex

Даты:

Поступила в редакцию:	2 дек. 2019 г.
Принята к публикации:	25 мая 2020 г.

Идентификаторы БД: Нет идентификаторов

Цитирование в БД: Пока нет цитирований