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

18 с.

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

алгоритм с постоянной оценкой точности, асимметричная задача коммивояжера, задача коммивояжера с призами, задача маршрутизации транспорта, задача о штейнеровском цикле минимального веса, обобщенная задача коммивояжера, полиномиальная сводимость, Asymmetric traveling salesman problem, constant-factor approximation algorithm, Generalized traveling salesman problem, Polynomial-time reduction, prize collecting traveling salesman problem, Steiner Cycle Problem, vehicle routing problem

Русский

Труды института математики и механики УрО РАН. – 2022. – № 3. – С. 241–258.