Geodesic
Efficient approximation of the capacitated vehicle routing problem in a metric space of an arbitrary fixed doubling dimension
Doklady Rossijskoj akademii nauk. Matematika, informatika, processy upravleniâ, Tome 493 (2020), pp. 74-80 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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.
Keywords: capacitated vehicle routing problem, metric spaces of a fixed doubling dimension
Mots-clés : quasi-polynomial time approximation scheme. 
@article{DANMA_2020_493_a14,
     author = {M. Yu. Khachay and Yu. Yu. Ogorodnikov},
     title = {Efficient approximation of the capacitated vehicle routing problem in a metric space of an arbitrary fixed doubling dimension},
     journal = {Doklady Rossijskoj akademii nauk. Matematika, informatika, processy upravleni\^a},
     pages = {74--80},
     year = {2020},
     volume = {493},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DANMA_2020_493_a14/}
}
TY  - JOUR
AU  - M. Yu. Khachay
AU  - Yu. Yu. Ogorodnikov
TI  - Efficient approximation of the capacitated vehicle routing problem in a metric space of an arbitrary fixed doubling dimension
JO  - Doklady Rossijskoj akademii nauk. Matematika, informatika, processy upravleniâ
PY  - 2020
SP  - 74
EP  - 80
VL  - 493
UR  - http://geodesic.mathdoc.fr/item/DANMA_2020_493_a14/
LA  - ru
ID  - DANMA_2020_493_a14
ER  - 
%0 Journal Article
%A M. Yu. Khachay
%A Yu. Yu. Ogorodnikov
%T Efficient approximation of the capacitated vehicle routing problem in a metric space of an arbitrary fixed doubling dimension
%J Doklady Rossijskoj akademii nauk. Matematika, informatika, processy upravleniâ
%D 2020
%P 74-80
%V 493
%U http://geodesic.mathdoc.fr/item/DANMA_2020_493_a14/
%G ru
%F DANMA_2020_493_a14
M. Yu. Khachay; Yu. Yu. Ogorodnikov. Efficient approximation of the capacitated vehicle routing problem in a metric space of an arbitrary fixed doubling dimension. Doklady Rossijskoj akademii nauk. Matematika, informatika, processy upravleniâ, Tome 493 (2020), pp. 74-80. http://geodesic.mathdoc.fr/item/DANMA_2020_493_a14/

[1] Dantzig G.B., Ramser J.H., Management science, 6:1 (1959), 80–91 | DOI | MR | Zbl

[2] Papadimitriou C., Theoret. Comput. Sci., 4 (1977), 237–244 | DOI | MR | Zbl

[3] Haimovich M., Rinnooy Kan A.H.G., Mathematics of Operations Research, 10:4 (1985), 527–542 | DOI | MR | Zbl

[4] Asano T., Katoh N., Tamaki H., Tokuyama T., Proc. 29th Annual ACM Symposium on Theory of Computing, STOC '97, 1997, 275–283

[5] Khachai M., Ogorodnikov Y., Trudy Instituta Matematiki i Mekhaniki UrO RAN, 25, no. 4, 2019, 235–248 | DOI | MR

[6] Adamaszek A., Czumaj A., Lingas A., Int. J. Foundations of Computer Science, 21:6 (2010), 893–904 | DOI | MR | Zbl

[7] Khachay M., Ogorodnikov Y., Analysis of Images, Social Networks and Texts, 7th Intern. Conf. AIST-2018, LNCS, 11179, 2018, 318–328

[8] Khachai M., Ogorodnikov Y., Proc. of the Steklov Institute of Mathematics, 307, suppl. 1 (2019), S51–S63 | DOI | MR | Zbl

[9] Khachay M. , Ogorodnikov Y., Mathematical Optimization Theory and Operations Research, 18th International conference (MOTOR 2019), Proceedings, LNCS, 11548, 2019, 309–327 | MR | Zbl

[10] Das A., Mathieu C., Algorithmica, 73 (2015), 115–142 | DOI | MR | Zbl

[11] Abraham I., Bartal Y., Neiman O., Advances in Mathematics, 228:6 (2011), 3026–3126 | DOI | MR | Zbl

[12] Talwar K., Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, STOC'04, 2004, 281–290 | DOI | Zbl

[13] Bartal Y., Gottlieb L.A., Krauthgamer R., SIAM J. on Computing, 45 (2016), 1563–1581 | DOI | MR | Zbl

[14] Arora S., J. ACM, 45 (1998), 753–782 | DOI | MR | Zbl