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

Хачай М. Ю. Приближенные алгоритмы с постоянной точностью для серии маршрутных комбинаторных задач, основанные на сведении к асимметричной задаче коммивояжера / М. Ю. Хачай, Е. Д. Незнахина, К. В. Рыженко // Труды Института математики и механики УрО РАН. - Екатеринбург, 2022. - Том 28, № 3. - С. 241-258.

Документ доступен в ЦНБ УрО РАН: 

Нет

Год: 

2022

Связанные персоналии: 

Нет

Рубрики: 

  • Математика

Вид издания: 

  • статья из сборника


h1

Публичные страницы

Публичные страницы

Аннотация

Аннотация

В статье впервые обосновываются алгоритмы с постоянными гарантированными оценками точности для серии асимметричных маршрутных задач комбинаторной оптимизации: задачи о штейнеровском цикле (SCP), обобщенной задачи коммивояжера (GTSP), задачи маршрутизации транспорта с неделимым потребительским спросом (CVRP-UCD) и задачи коммивояжера с призами (PCTSP). Объединяет представленные результаты то, что все они опираются на полиномиальную сводимость, сохраняющую стоимость (cost-preserving reduction), исследуемых задач к подходящим постановкам асимметричной задачи коммивояжера (ATSP) и (22 + ε) - приближенный алгоритм для этой классической задачи, предложенный О. Свенссоном и В. Трауб в 2019 г. For the first time, algorithms with constant performance guarantees are substantiated for a series of asymmetric routing problems of combinatorial optimization: Steiner Cycle Problem (SCP), Generalized Traveling Salesman Problem (GTSP), Capacitated Vehicle Routing Problem with Unsplittable Client Demands (CVRP-UCD), and Prize Collecting Traveling Salesman Problem (PCTSP). The presented results are united by the property that they all rely on polynomial cost-preserving reduction to appropriate statements of Asymmetric Traveling Salesman Problem (ATSP) and on the (22 + ε)-approximate algorithm for this classical problem proposed by O. Svensson and V. Traub in 2019.