M. Yu. Khachay, Yu. Yu. Ogorodnikov, “Efficient approximation of the capacitated vehicle routing problem in a metric space of an arbitrary fixed doubling dimension”, Dokl. RAN. Math. Inf. Proc. Upr., 2020, Volume 493,Pages <nobr>74

This article is cited in 5 papers

INFORMATICS

Efficient approximation of the capacitated vehicle routing problem in a metric space of an arbitrary fixed doubling dimension

M. Yu. Khachay^abc, Yu. Yu. Ogorodnikov^ab

^a N.N. Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Ekaterinburg, Russian Federation
^b Ural Federal University named after the First President of Russia B. N. Yeltsin, Ekaterinburg, Russian Federation
^c Omsk State University, Omsk, Russian Federation

Abstract: In this paper, for the first time, we provide a quasi-polynomial time approximation scheme for the well-known capacitated vehicle routing problem formulated in metric spaces of an arbitrary fixed doubling dimension.

Keywords: capacitated vehicle routing problem, metric spaces of a fixed doubling dimension, quasi-polynomial time approximation scheme.

UDC: 519.8

Presented: K. V. Rudakov
Received: 26.05.2020
Revised: 01.06.2020
Accepted: 02.06.2020

DOI: 10.31857/S2686954320040086