Приближенные алгоритмы с постоянной точностью для серии маршрутных комбинаторных задач, основанные на сведении к асимметричной задаче коммивояжера

В статье впервые обосновываются алгоритмы с постоянными гарантированными оценками точности для серии асимметричных маршрутных задач комбинаторной оптимизации: задачи о штейнеровском цикле (SCP), обобщенной задачи коммивояжера (GTSP), задачи маршрутизации транспорта с неделимым потребительским спросом (CVRP-UCD) и задачи коммивояжера с призами (PCTSP). Объединяет представленные результаты то, что все они опираются на полиномиальную сводимость, сохраняющую стоимость (cost-preserving reduction), исследуемых задач к подходящим постановкам асимметричной задачи коммивояжера (ATSP) и $(22+\varepsilon)$-приближенный алгоритм для этой классической задачи, предложенный О. Свенссоном и В. Трауб в 2019 г.