Полиномиальная аппроксимируемость асимметричной задачи о покрытии графа ограниченным числом циклов

В недавних работах О. Свенссона и В. Трауб впервые обоснована аппроксимируемость асимметричной задачи коммивояжера (ATSP) в классе алгоритмов с фиксированными гарантиями точности. Как и знаменитый алгоритм Кристофидеса — Сердюкова для симметричных маршрутных задач, данные прорывные результаты, применяемые в качестве “черного ящика”, позволили разработать первые полиномиальные приближенные алгоритмы с константными факторами аппроксимации для серии близких комбинаторных задач. Одновременно выявились задачи, в которых этот простой подход, основанный на сведении исходной задачи к одной или нескольким вспомогательным постановкам задачи коммивояжера, не приводит к успеху. В данной статье подход Свенссона — Трауб распространяется на более широкий класс задач о покрытии минимального веса взвешенного ориентированного графа ограниченным сверху числом циклов. В частности, впервые показывается, что задача о покрытии графа не более чем $k$ циклами допускает полиномиальную аппроксимацию с константной точностью $\max\{22+\varepsilon, 4 + k\}$ для произвольного $\varepsilon>0$.