Просмотр исходного текста страницы Arxiv/Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway Dimension 2021 2106.15034

{{checked|}}
{{arxivlink|arxiv/Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway Dimension 2021 2106.15034|2=
В этой статье мы представляем схемы аппроксимации для емкостного транспортного средства. Задача маршрутизации (CVRP) на нескольких классах графов. В CVRP, представленный Данциг и Рамзер (1959), нам дан график ''G=(V,E)'' с метрическими краями затраты, депо ''r∈V'', и автомобиль ограниченной вместимости Q. 

Цель состоит в том, чтобы найти минимальную стоимость туров для автомобиля, который возвращается в депо, каждое посещение не более Q узлы, так что они покрывают все узлы. Это обобщает классический TSP и был тщательно изучен. В более общие настройки, каждый узел v имеет спрос d v и общий спрос каждого тур должен быть не более Q. 

Либо спрос каждого узла должен обслуживаться один тур (неразделимый) или может обслуживаться несколькими турами (разделенный). В самый известный алгоритм аппроксимации общих графиков имеет соотношение ''α + 2 (1-ϵ)'' (для нерасщепляемого) и ''α + 1 - ϵ'' (для ''splittable'') для некоторых фиксированных ''ϵ > 1/3000'', где а это наилучшее приближение для TSP. 

Даже для деревьев наилучшее приближение соотношение ''4 / 3'' Беккера (2018), и вопрос о существовании схема аппроксимации для этого простого класса графов. 

Дас и Матье (2015) представили схему аппроксимации со временем п журнал ''O\log^{(1/ϵ)п}'' за Евклидова плоскость R^2. Никакой другой схемы аппроксимации не известно ни для одного другой класс метрик (без дополнительных ограничений на Q). 

В этой статье мы добиться значительного прогресса в решении этой классической проблемы, представив Квазиполиномиальные схемы аппроксимации времени (QPTAS) для графов ограниченного Treewidth, графики ограниченных размеров автомагистралей и графики ограниченного удвоения габаритные размеры. 

Для сравнения наш результат представляет собой схему аппроксимации для Евклидов самолет со временем выполнения ''n O(\log^{10}{n/ϵ^9})''. 
}}
{{enddiv}}

[[Категория:ArxivArticles]]