Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс:
http://elar.urfu.ru/handle/10995/101577
Название: | Haimovich-Rinnooy Kan polynomial-time approximation scheme for the CVRP in metric spaces of a fixed doubling dimension Аппроксимационная схема Хаймовича - Ринноя Кана для CVRP в метрических пространствах фиксированной размерности удвоения |
Авторы: | Khachai, M. Y. Ogorodnikov, Y. Y. |
Дата публикации: | 2019 |
Издатель: | Krasovskii Institute of Mathematics and Mechanics |
Библиографическое описание: | 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. |
Аннотация: | 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. |
Ключевые слова: | CAPACITATED VEHICLE ROUTING PROBLEM (CVRP) DOUBLING DIMENSION METRIC SPACE POLYNOMIAL-TIME APPROXIMATION SCHEME (PTAS) |
URI: | http://elar.urfu.ru/handle/10995/101577 |
Условия доступа: | info:eu-repo/semantics/openAccess |
Идентификатор РИНЦ: | 41455540 |
Идентификатор SCOPUS: | 85078525096 |
Идентификатор PURE: | 11465228 |
ISSN: | 1344889 |
DOI: | 10.21538/0134-4889-2019-25-4-235-248 |
Располагается в коллекциях: | Научные публикации ученых УрФУ, проиндексированные в SCOPUS и WoS CC |
Файлы этого ресурса:
Файл | Описание | Размер | Формат | |
---|---|---|---|---|
2-s2.0-85078525096.pdf | 259,78 kB | Adobe PDF | Просмотреть/Открыть |
Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.