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

Эта публикация цитируется в 2 статьях

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

А. Н. Глебов^ab, С. Г. Токтохоева^b

^a Институт математики им. С. Л. Соболева, пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
^b Новосибирский государственный университет, ул. Пирогова, 1, 630090 Новосибирск, Россия

Аннотация: Разработан первый полиномиальный приближённый алгоритм с гарантированной оценкой точности для несимметричного случая задачи о трёх коммивояжёрах на максимум, где требуется найти три рёберно непересекающихся гамильтоновых цикла максимального суммарного веса в полном взвешенном ориентированном графе. Для полученного алгоритма обоснована гарантированная оценка точности $\frac 35$ и кубическая оценка временной сложности. Ил. 18, библиогр. 27.

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

УДК: 519.8

Статья поступила: 06.06.2018
Переработанный вариант: 27.11.2018
Принята к публикации: 28.11.2018

DOI: 10.33048/daio.2019.26.622