Arxiv/Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway Dimension 2021 2106.15034
«Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway Dimension 2021 2106.15034»скачать
Цель состоит в том, чтобы найти минимальную стоимость туров для автомобиля, который возвращается в депо, каждое посещение не более 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}).…»
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.