EN|RU

Том 18, номер 5, 2011 г., Стр. 11-37

УДК 519.8
Глебов A. Н., Замбалаева Д. Ж.
Приближённый алгоритм решения задачи о двух коммивояжёрах на минимум с различными весовыми функциями

Аннотация:
Основной результат статьи — приближённый алгоритм с оценкой временнóй сложности O(n5) и оценкой точности 4/3 (без учёта аддитивной константы) для задачи о поиске двух рёберно непересекающихся гамильтоновых циклов минимального суммарного веса в полном n-вершинном графе с весами рёбер 1 и 2 в случае, когда весовые функции рёбер этих циклов различны (задача о двух коммивояжёрах на минимум с весами рёбер 1 и 2). Этот результат улучшает ранее установленную для задачи оценку точности 11/7.
Ил. 3, библиогр. 10.

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

Глебов Алексей Николаевич 1,2
Замбалаева Долгор Жамьяновна 1

1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: angle@math.nsc.ru, dolgor@ngs.ru

Статья поступила 23 июня 2011 г.

 © Институт математики им. С. Л. Соболева, 2015