|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
Полиномиальный $3/5$-приближённый алгоритм для несимметричной задачи о трёх коммивояжёрах на максимум
А. Н. Глебовab, С. Г. Токтохоеваb a Институт математики им. С. Л. Соболева, пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
b Новосибирский государственный университет, ул. Пирогова, 1, 630090 Новосибирск, Россия
Аннотация:
Разработан первый полиномиальный приближённый алгоритм с гарантированной оценкой точности для несимметричного случая задачи о трёх коммивояжёрах на максимум, где требуется найти три рёберно непересекающихся гамильтоновых цикла максимального суммарного веса в полном взвешенном ориентированном графе. Для полученного алгоритма обоснована гарантированная оценка точности $\frac 35$ и кубическая оценка временной сложности. Ил. 18, библиогр. 27.
Ключевые слова:
гамильтонов цикл, задача коммивояжёра, задача нескольких коммивояжёров, приближённый алгоритм, гарантированная оценка точности.
Статья поступила: 06.06.2018 Переработанный вариант: 27.11.2018 Принята к публикации: 28.11.2018
Образец цитирования:
А. Н. Глебов, С. Г. Токтохоева, “Полиномиальный $3/5$-приближённый алгоритм для несимметричной задачи о трёх коммивояжёрах на максимум”, Дискретн. анализ и исслед. опер., 26:2 (2019), 30–59; J. Appl. Industr. Math., 13:2 (2019), 219–238
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da922 https://www.mathnet.ru/rus/da/v26/i2/p30
|
Статистика просмотров: |
Страница аннотации: | 216 | PDF полного текста: | 57 | Список литературы: | 25 | Первая страница: | 6 |
|