Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/101577
Title: Haimovich-Rinnooy Kan polynomial-time approximation scheme for the CVRP in metric spaces of a fixed doubling dimension
Аппроксимационная схема Хаймовича - Ринноя Кана для CVRP в метрических пространствах фиксированной размерности удвоения
Authors: Khachai, M. Y.
Ogorodnikov, Y. Y.
Issue Date: 2019
Publisher: Krasovskii Institute of Mathematics and Mechanics
Citation: Khachai M. Y. Haimovich-Rinnooy Kan polynomial-time approximation scheme for the CVRP in metric spaces of a fixed doubling dimension / M. Y. Khachai, Y. Y. Ogorodnikov. — DOI 10.21538/0134-4889-2019-25-4-235-248 // Trudy Instituta Matematiki i Mekhaniki UrO RAN. — 2019. — Vol. 25. — Iss. 4. — P. 235-248.
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.
Keywords: CAPACITATED VEHICLE ROUTING PROBLEM (CVRP)
DOUBLING DIMENSION
METRIC SPACE
POLYNOMIAL-TIME APPROXIMATION SCHEME (PTAS)
URI: http://hdl.handle.net/10995/101577
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 85078525096
PURE ID: 11465228
ISSN: 1344889
DOI: 10.21538/0134-4889-2019-25-4-235-248
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-85078525096.pdf259,78 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.