1. Haimovich-Rinnooy Kan polynomial-time approximation scheme for the CVRP in metric spaces of a fixed doubling dimension
- Author
-
M. Y. Khachai and Y. Y. Ogorodnikov
- Subjects
Discrete mathematics ,Applied Mathematics ,General Mathematics ,Computational Mechanics ,METRIC SPACE ,Polynomial-time approximation scheme ,Computer Science Applications ,Metric space ,Dimension (vector space) ,POLYNOMIAL-TIME APPROXIMATION SCHEME (PTAS) ,TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY ,DOUBLING DIMENSION ,CAPACITATED VEHICLE ROUTING PROBLEM (CVRP) ,Mathematics ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
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 ≥ 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. © 2019 Krasovskii Institute of Mathematics and Mechanics. All right reserved.
- Published
- 2019