|
Дискретный анализ и исследование операций, 2014, том 21, выпуск 6, страницы 11–20
(Mi da798)
|
|
|
|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)
$2/3$-приближённый алгоритм для несимметричной задачи о двух коммивояжёрах на максимум
А. Н. Глебов, Д. Ж. Замбалаева, А. А. Скретнева Институт математики им. С. Л. Соболева СО РАН, пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
Аннотация:
Получен приближённый алгоритм с оценкой точности $2/3$ и кубической оценкой временнóй сложности для несимметричной задачи о двух коммивояжёрах на максимум, состоящей в поиске двух рёберно непересекающихся гамильтоновых циклов с максимальным суммарным весом рёбер в полном ориентированном графе. Ил. 5, библиогр. 7.
Ключевые слова:
задача коммивояжёра, задача о двух коммивояжёрах, полиномиальный алгоритм, гарантированная оценка точности, ориентированный граф.
Статья поступила: 02.12.2013 Переработанный вариант: 11.07.2014
Образец цитирования:
А. Н. Глебов, Д. Ж. Замбалаева, А. А. Скретнева, “$2/3$-приближённый алгоритм для несимметричной задачи о двух коммивояжёрах на максимум”, Дискретн. анализ и исслед. опер., 21:6 (2014), 11–20; J. Appl. Industr. Math., 9:1 (2015), 61–67
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da798 https://www.mathnet.ru/rus/da/v21/i6/p11
|
Статистика просмотров: |
Страница аннотации: | 228 | PDF полного текста: | 195 | Список литературы: | 26 | Первая страница: | 3 |
|