|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Полиномиальная аппроксимируемость асимметричной задачи о покрытии графа ограниченным числом циклов
М. Ю. Хачайa, Е. Д. Незнахинаab, К. В. Рыженкоa a Институт математики и механики им. Н. Н. Красовского Уральского отделения РАН, г. Екатеринбург
b Уральский федеральный университет им. первого Президента России Б. Н. Ельцина, г. Екатеринбург
Аннотация:
В недавних работах О. Свенссона и В. Трауб впервые обоснована
аппроксимируемость асимметричной задачи коммивояжера (ATSP)
в классе алгоритмов с фиксированными гарантиями точности.
Как и знаменитый алгоритм Кристофидеса — Сердюкова
для симметричных маршрутных задач, данные прорывные результаты,
применяемые в качестве “черного ящика”, позволили разработать
первые полиномиальные приближенные алгоритмы с константными
факторами аппроксимации для серии близких комбинаторных задач.
Одновременно выявились задачи, в которых этот простой подход,
основанный на сведении исходной задачи к одной или нескольким вспомогательным постановкам задачи коммивояжера, не приводит к успеху.
В данной статье подход Свенссона — Трауб
распространяется на более широкий класс задач о покрытии
минимального веса взвешенного ориентированного графа
ограниченным сверху числом циклов.
В частности, впервые показывается, что задача о покрытии графа
не более чем $k$ циклами допускает полиномиальную аппроксимацию
с константной точностью
$\max\{22+\varepsilon, 4 + k\}$
для произвольного $\varepsilon>0$.
Ключевые слова:
цикловое покрытие графа, асимметричная задача коммивояжера, приближенный алгоритм с константным фактором аппроксимации.
Поступила в редакцию: 04.08.2023 Исправленный вариант: 18.08.2023 Принята в печать: 21.08.2023
Образец цитирования:
М. Ю. Хачай, Е. Д. Незнахина, К. В. Рыженко, “Полиномиальная аппроксимируемость асимметричной задачи о покрытии графа ограниченным числом циклов”, Тр. ИММ УрО РАН, 29, № 3, 2023, 261–273; Proc. Steklov Inst. Math. (Suppl.), 323, suppl. 1 (2023), S121–S132
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/timm2030 https://www.mathnet.ru/rus/timm/v29/i3/p261
|
Статистика просмотров: |
Страница аннотации: | 79 | PDF полного текста: | 13 | Список литературы: | 21 | Первая страница: | 3 |
|