Back to Search
Start Over
Haimovich-Rinnooy Kan polynomial-time approximation scheme for the CVRP in metric spaces of a fixed doubling dimension
- Source :
- Tr. Inst. Mat. Meh. UrO RAN, Trudy Instituta Matematiki i Mekhaniki UrO RAN
- Publication Year :
- 2019
- Publisher :
- Krasovskii Institute of Mathematics and Mechanics, 2019.
-
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.
- 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
Subjects
Details
- Language :
- Russian
- Database :
- OpenAIRE
- Journal :
- Tr. Inst. Mat. Meh. UrO RAN, Trudy Instituta Matematiki i Mekhaniki UrO RAN
- Accession number :
- edsair.doi.dedup.....285197ae099d90c3235f4fd650f05cae