Аппроксимационная схема Хаймовича - Ринноя Кана для CVRP в метрических пространствах фиксированной размерности удвоения

Задача маршрутизации транспорта с ограничением на грузоподъемность (Capacitated Vehicle Routing Problem, CVRP) — одна из классических маршрутных экстремальных комбинаторных задач, обладающих большим числом приложений в области исследования операций. Оставаясь NP-трудной в сильном смысле как в общем случае, так и на евклидовой плоскости, задача CVRP допускает квазиполиномиальные и даже полиномиальные приближенные схемы (QPTAS и PTAS) в евклидовых пространствах фиксированной размерности. В то же время метрическая постановка задачи APX-полна даже в случае произвольной фиксированной грузоподъемности $q\geq 3$. В данной работе показывается, что классический алгоритм М. Хаймовича и А. Ринноя Кана реализует полиномиальную приближенную схему PTAS и эффективную полиномиальную приближенную схему (EPTAS) в произвольном метрическом пространстве фиксированной размерности при $q=o(\log\log n)$ и произвольной постоянной грузоподъемности соответственно.