Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/101577
Full metadata record
DC FieldValueLanguage
dc.contributor.authorKhachai, M. Y.en
dc.contributor.authorOgorodnikov, Y. Y.en
dc.date.accessioned2021-08-31T14:58:15Z-
dc.date.available2021-08-31T14:58:15Z-
dc.date.issued2019-
dc.identifier.citationKhachai 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.en
dc.identifier.issn1344889-
dc.identifier.otherFinal2
dc.identifier.otherAll Open Access, Bronze3
dc.identifier.otherhttps://www.scopus.com/inward/record.uri?eid=2-s2.0-85078525096&doi=10.21538%2f0134-4889-2019-25-4-235-248&partnerID=40&md5=2215e072d0403571c26b4b9aeee559dc
dc.identifier.otherhttp://journal.imm.uran.ru/sites/default/files/content/25_4/TrIMMUrORAN_2019_4_p235_L.pdfm
dc.identifier.urihttp://hdl.handle.net/10995/101577-
dc.description.abstractThe 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.en
dc.format.mimetypeapplication/pdfen
dc.language.isoruen
dc.publisherKrasovskii Institute of Mathematics and Mechanicsen
dc.rightsinfo:eu-repo/semantics/openAccessen
dc.sourceTr. Inst. Mat. Meh. UrO RAN2
dc.sourceTrudy Instituta Matematiki i Mekhaniki UrO RANen
dc.subjectCAPACITATED VEHICLE ROUTING PROBLEM (CVRP)en
dc.subjectDOUBLING DIMENSIONen
dc.subjectMETRIC SPACEen
dc.subjectPOLYNOMIAL-TIME APPROXIMATION SCHEME (PTAS)en
dc.titleHaimovich-Rinnooy Kan polynomial-time approximation scheme for the CVRP in metric spaces of a fixed doubling dimensionen
dc.titleАппроксимационная схема Хаймовича - Ринноя Кана для CVRP в метрических пространствах фиксированной размерности удвоенияru
dc.typeArticleen
dc.typeinfo:eu-repo/semantics/articleen
dc.typeinfo:eu-repo/semantics/publishedVersionen
dc.identifier.doi10.21538/0134-4889-2019-25-4-235-248-
dc.identifier.scopus85078525096-
local.contributor.employeeKhachai, M.Y., Krasovskii Institute of Mathematics, Mechanics of the Ural Branch, Russian Academy of Sciences, Yekaterinburg, 620108, Russian Federation, Ural Federal University, Yekaterinburg620083, Russian Federation, Omsk State Technical University, Omsk, 644050, Russian Federation
local.contributor.employeeOgorodnikov, Y.Y., Krasovskii Institute of Mathematics, Mechanics of the Ural Branch, Russian Academy of Sciences, Yekaterinburg, 620108, Russian Federation, Ural Federal University, Yekaterinburg620083, Russian Federation
local.description.firstpage235-
local.description.lastpage248-
local.issue4-
local.volume25-
local.contributor.departmentKrasovskii Institute of Mathematics, Mechanics of the Ural Branch, Russian Academy of Sciences, Yekaterinburg, 620108, Russian Federation
local.contributor.departmentUral Federal University, Yekaterinburg620083, Russian Federation
local.contributor.departmentOmsk State Technical University, Omsk, 644050, Russian Federation
local.identifier.pure11465228-
local.identifier.eid2-s2.0-85078525096-
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.