Abstract
In this paper, for the first time, we provide a quasi-polynomial time approximation scheme for the well-known capacitated vehicle routing problem formulated in metric spaces of an arbitrary fixed doubling dimension.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
Here and below, we follow the well-known RAM model of computing, in which an arbitrary elementary operation over real numbers is assumed to have constant complexity.
Where \({{p}^{{{\text{in}}}}} = {{p}^{{{\text{in}}}}}(\sigma )\) and \({{p}^{{{\text{out}}}}} = {{p}^{{{\text{out}}}}}(\sigma )\) are suitable portals.
REFERENCES
G. B. Dantzig and J. H. Ramser, Manage. Sci. 6, 80–91 (1959).
C. Papadimitriou, Theor. Comput. Sci. 4, 237–244 (1977).
M. Haimovich and A. H. G. Rinnooy Kan, Math. Oper. Res. 10, 527–542 (1985).
T. Asano, N. Katoh, H. Tamaki, and T. Tokuyama, in Proceedings of the 29th Annual ACM Symposium on Theory of Computing, STOC’97 (1997), pp. 275–283.
M. Khachay and Y. Ogorodnikov, Tr. Inst. Mat. Mekh. Ural. Otd. Ross. Akad. Nauk 25, 235–248 (2019).
A. Adamaszek, A. Czumaj, and A. Lingas, Int. J. Found. Comput. Sci. 21, 893–904 (2010).
M. Khachay and Y. Ogorodnikov, in Analysis of Images, Social Networks, and Texts: 7th International Conference AIST-2018, Lect. Notes Comput. Sci. 11179, 318–328 (2018).
M. Khachai and Y. Ogorodnikov, Proc. Steklov Inst. Math. 307, Suppl. 1, S51–S63 (2019).
M. Khachay and Y. Ogorodnikov, in Mathematical Optimization Theory and Operations Research: Proceedings of the 18th International Conference (MOTOR 2019), Lect. Notes Comput. Sci. 11548, 309–327 (2019).
A. Das and C. Mathieu, Algorithmica 73, 115–142 (2015).
I. Abraham, Y. Bartal, and O. Neiman, Adv. Math. 228, 3026–3126 (2011).
K. Talwar, in Proceedings of the 36th Annual ACM Symposium on Theory of Computing, STOC’04 (2004), pp. 281–290.
Y. Bartal, L. A. Gottlieb, and R. Krauthgamer, SIAM J. Comput. 45, 1563–1581 (2016).
S. Arora, J. ACM 45, 753–782 (1998).
Funding
This work was performed within the research carried out at the Ural Mathematical Center and was supported by the Russian Foundation for Basic Research, grant no. 19-07-01243.
Author information
Authors and Affiliations
Corresponding authors
Additional information
Translated by I. Ruzanova
Rights and permissions
About this article
Cite this article
Khachay, M.Y., Ogorodnikov, Y.Y. Efficient Approximation of the Capacitated Vehicle Routing Problem in a Metric Space of an Arbitrary Fixed Doubling Dimension. Dokl. Math. 102, 324–329 (2020). https://doi.org/10.1134/S1064562420040080
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S1064562420040080