Эффективная аппроксимируемость задачи маршрутизации транспорта в метрических пространствах фиксированной размерности удвоения

Задача маршрутизации транспорта ограниченной грузоподъемности (Capacitated Vehicle Routing Problem, CVRP) — одна из классических проблем комбинаторной оптимизации, обладающая широким спектром важных практических приложений в исследовании операций. Как и большинство известных комбинаторных задач, CVRP NP-трудна в сильном смысле и сохраняет труднорешаемость даже на евклидовой плоскости. Поэтому одно из актуальных направлений в области алгоритмического анализа задачи связано с проектированием полиномиальных приближенных алгоритмов с теоретическими оценками точности и трудоемкости. По аналогии с классической задачей коммивояжера (Traveling Salesman Problem, TSP) задача маршрутизации неаппроксимируема в общем случае (при условии $P\neq NP$), APX-полна при произвольной метрике и допускает квазиполиномиальные и даже полиномиальные приближенные схемы в конечномерных числовых пространствах. Недавние работы Талвара и Бартала, Готтлиба и Краутгеймера, обобщающие классический результат Ароры, позволили существенно расширить класс метрических постановок задачи коммивояжера, для которых удается обосновать существование полиномиальных приближенных схем.
В развитие родственного подхода в настоящем сообщении обосновывается аппроксимируемость в классе квазиполиномиальных приближенных схем метрической задачи маршрутизации транспорта, заданной в пространстве произвольной фиксированной размерности удвоения.