Geodesic
Haimovich-Rinnooy Kan polynomial-time approximation scheme for the CVRP in metric spaces of a fixed doubling dimension
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 25 (2019) no. 4, pp. 235-248

Voir la notice de l'article provenant de la source Math-Net.Ru

The Capacitated Vehicle Routing Problem (CVRP) is a classical extremal combinatorial routing problem with numerous applications in operations research. Although the CVRP is strongly NP-hard both in the general case and in the Euclidean plane, it admits quasipolynomial- and even polynomial-time approximation schemes (QPTAS and PTAS) in Euclidean spaces of fixed dimension. At the same time, the metric setting of the problem is APX-complete even for an arbitrary fixed capacity $q\geq 3$. In this paper, we show that the classical Haimovich–Rinnooy Kan algorithm implements a PTAS and an Efficient Polynomial-Time Approximation Scheme (EPTAS) in an arbitrary metric space of fixed doubling dimension for $q=o(\log\log n)$ and for an arbitrary constant capacity, respectively.
Keywords: Capacitated Vehicle Routing Problem (CVRP), Polynomial-Time Approximation Scheme (PTAS), metric space, doubling dimension. 
@article{TIMM_2019_25_4_a24,
     author = {M. Yu. Khachay and Yu. Yu. Ogorodnikov},
     title = {Haimovich-Rinnooy {Kan} polynomial-time approximation scheme for the {CVRP} in metric spaces of a fixed doubling dimension},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {235--248},
     publisher = {mathdoc},
     volume = {25},
     number = {4},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2019_25_4_a24/}
}
TY  - JOUR
AU  - M. Yu. Khachay
AU  - Yu. Yu. Ogorodnikov
TI  - Haimovich-Rinnooy Kan polynomial-time approximation scheme for the CVRP in metric spaces of a fixed doubling dimension
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2019
SP  - 235
EP  - 248
VL  - 25
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TIMM_2019_25_4_a24/
LA  - ru
ID  - TIMM_2019_25_4_a24
ER  - 
%0 Journal Article
%A M. Yu. Khachay
%A Yu. Yu. Ogorodnikov
%T Haimovich-Rinnooy Kan polynomial-time approximation scheme for the CVRP in metric spaces of a fixed doubling dimension
%J Trudy Instituta matematiki i mehaniki
%D 2019
%P 235-248
%V 25
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TIMM_2019_25_4_a24/
%G ru
%F TIMM_2019_25_4_a24
M. Yu. Khachay; Yu. Yu. Ogorodnikov. Haimovich-Rinnooy Kan polynomial-time approximation scheme for the CVRP in metric spaces of a fixed doubling dimension. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 25 (2019) no. 4, pp. 235-248. http://geodesic.mathdoc.fr/item/TIMM_2019_25_4_a24/