Geodesic
Алгоритмы приближённого решения задачи о~двух коммивояжёрах в~полном графе с~весами рёбер~1 и~2
Diskretnyj analiz i issledovanie operacij, Tome 14 (2007) no. 2, pp. 41-61.

Voir la notice de l'article provenant de la source Math-Net.Ru

@article{DA_2007_14_2_a3,
     author = {E. Kh. Gimadi and Yu. V. Glazkov and A. N. Glebov},
     title = {{\CYRA}{\cyrl}{\cyrg}{\cyro}{\cyrr}{\cyri}{\cyrt}{\cyrm}{\cyrery} {\cyrp}{\cyrr}{\cyri}{\cyrb}{\cyrl}{\cyri}{\cyrzh}{\cyryo}{\cyrn}{\cyrn}{\cyro}{\cyrg}{\cyro} {\cyrr}{\cyre}{\cyrsh}{\cyre}{\cyrn}{\cyri}{\cyrya} {\cyrz}{\cyra}{\cyrd}{\cyra}{\cyrch}{\cyri} {\cyro}~{\cyrd}{\cyrv}{\cyru}{\cyrh} {\cyrk}{\cyro}{\cyrm}{\cyrm}{\cyri}{\cyrv}{\cyro}{\cyrya}{\cyrzh}{\cyryo}{\cyrr}{\cyra}{\cyrh} {\cyrv}~{\cyrp}{\cyro}{\cyrl}{\cyrn}{\cyro}{\cyrm} {\cyrg}{\cyrr}{\cyra}{\cyrf}{\cyre} {\cyrs}~{\cyrv}{\cyre}{\cyrs}{\cyra}{\cyrm}{\cyri} {\cyrr}{\cyryo}{\cyrb}{\cyre}{\cyrr}~1 {\cyri}~2},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {41--61},
     publisher = {mathdoc},
     volume = {14},
     number = {2},
     year = {2007},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2007_14_2_a3/}
}
TY  - JOUR
AU  - E. Kh. Gimadi
AU  - Yu. V. Glazkov
AU  - A. N. Glebov
TI  - Алгоритмы приближённого решения задачи о~двух коммивояжёрах в~полном графе с~весами рёбер~1 и~2
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2007
SP  - 41
EP  - 61
VL  - 14
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2007_14_2_a3/
LA  - ru
ID  - DA_2007_14_2_a3
ER  - 
%0 Journal Article
%A E. Kh. Gimadi
%A Yu. V. Glazkov
%A A. N. Glebov
%T Алгоритмы приближённого решения задачи о~двух коммивояжёрах в~полном графе с~весами рёбер~1 и~2
%J Diskretnyj analiz i issledovanie operacij
%D 2007
%P 41-61
%V 14
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2007_14_2_a3/
%G ru
%F DA_2007_14_2_a3
E. Kh. Gimadi; Yu. V. Glazkov; A. N. Glebov. Алгоритмы приближённого решения задачи о~двух коммивояжёрах в~полном графе с~весами рёбер~1 и~2. Diskretnyj analiz i issledovanie operacij, Tome 14 (2007) no. 2, pp. 41-61. http://geodesic.mathdoc.fr/item/DA_2007_14_2_a3/

[1] Ageev A. A., Baburin A. E., Gimadi E. Kh., “Polinomialnyi algoritm s otsenkoi 3/4 dlya nakhozhdeniya dvukh neperesekayuschikhsya gamiltonovykh tsiklov maksimalnogo summarnogo vesa”, Diskret. analiz i issled. operatsii. Ser. 1, 13:2 (2006), 11–20 | MR

[2] Baburin A. E., Gimadi E. Kh., Korkishko N. M., “Priblizhennye algoritmy dlya nakhozhdeniya dvukh reberno neperesekayuschikhsya gamiltonovykh tsiklov minimalnogo vesa”, Diskret. analiz i issled. operatsii. Ser. 2, 11:1 (2004), 11–25 | MR | Zbl

[3] Berman P., Karpinski M., “8/7 approximation algorithm for (1,2)-TSP”, Proc. of the 17th annual ACM–SIAM symposium on discrete algorithms, SODA 2006 (Miami, January 22–26, 2006), ACM Press, New York, 2006, 641–648

[4] Blaser M., Shankar Ram L., “An improved approximation algorithm for TSP with distances one and two”, Fundamentals of computation theory, Lecture Notes on Comput. Sci., 3623, Springer-Verlag, Berlin, 2005, 504–515 | MR

[5] Della Croce F., Paschos V. Th., Wolfler Calvo R., “Approximating the 2-peripatetic salesman problem”, 7th Workshop on modeling and algorithms for planning and scheduling problems, MAPSP 2005 (Siena, Italy, June 6–10, 2005), Springer-Verlag, Berlin, 2005, 114–116

[6] de Brey M. J. D., Volgenant A., “Well-solved cases of the 2-peripatetic salesman problem”, Optimization, 39:3 (1997), 275–293 | DOI | MR | Zbl

[7] de Kort J. B. J. M., “Lower bounds for symmetric $K$-peripatetic salesman problems”, Optimization, 22:1 (1991), 113–122 | DOI | MR | Zbl

[8] de Kort J. B. J. M., “Bounds for the symmetric 2-peripatetic salesman problem”, Optimization, 23:4 (1992), 357–367 | DOI | MR | Zbl

[9] de Kort J. B. J. M., “A branch and bound algorithm for symmetric\break 2-peripatetic salesman problems”, European J. Oper. Res., 70:2 (1993), 229–243 | DOI | MR | Zbl

[10] Duchenne E., Laporte G., Semet F., “Branch-and-cut algorithms for the undirected $m$-peripatetic salesman problem”, European J. Oper. Res., 162:3 (2005), 700–712 | DOI | MR | Zbl

[11] Gabow H. N., “An efficient reduction technique for degree-restricted subgraph and bidirected network flow problems”, Proc. 15th annual ACM simposium on theory of computing (Boston, April 25–27, 1983), ACM, New York, 1983, 448–456

[12] Krarup J., “The peripatetic salesman and some related unsolved problems”, Combinatorial programming: methods and applications, Reidel, Dordrecht, 1975, 173–178 | MR

[13] Papadimitriou C. H., Yannakakis M., “The traveling salesman problem with distances one and two”, Math. Oper. Res., 18:1 (1993), 1–11 | DOI | MR | Zbl