Geodesic
Approximation algorithms for maximum-weight problem of two-peripatetic salesmen
Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 1, pp. 17-32.

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

We consider the problem of finding two edge-disjoint Hamiltonian circuits (salesman routes) on maximum total weight in a complete undirected graph. In the case of edge weights in the interval $[1,q]$ a polynomial algorithm with performance ratio $\frac{3q+2}{4q+1}$ is constructed. In the case of different weight functions valued 1 and 2 a polynomial algorithm with performance ratio $\frac{11\rho-8}{18\rho-15}$ is presented, where $\rho$ is a guaranteed ratio of an algorithm for solving similar problem on minimum. Ill. 1, bibliogr. 13.
Keywords: traveling salesman problem, 2-peripatetic salesman problem, guaranteed approximation ratio.
Mots-clés : polynomial algorithm 
@article{DA_2012_19_1_a1,
     author = {E. Kh. Gimadi and E. V. Ivonina},
     title = {Approximation algorithms for maximum-weight problem of two-peripatetic salesmen},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {17--32},
     publisher = {mathdoc},
     volume = {19},
     number = {1},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2012_19_1_a1/}
}
TY  - JOUR
AU  - E. Kh. Gimadi
AU  - E. V. Ivonina
TI  - Approximation algorithms for maximum-weight problem of two-peripatetic salesmen
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2012
SP  - 17
EP  - 32
VL  - 19
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2012_19_1_a1/
LA  - ru
ID  - DA_2012_19_1_a1
ER  - 
%0 Journal Article
%A E. Kh. Gimadi
%A E. V. Ivonina
%T Approximation algorithms for maximum-weight problem of two-peripatetic salesmen
%J Diskretnyj analiz i issledovanie operacij
%D 2012
%P 17-32
%V 19
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2012_19_1_a1/
%G ru
%F DA_2012_19_1_a1
E. Kh. Gimadi; E. V. Ivonina. Approximation algorithms for maximum-weight problem of two-peripatetic salesmen. Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 1, pp. 17-32. http://geodesic.mathdoc.fr/item/DA_2012_19_1_a1/

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

[2] Gimadi E. Kh., Glazkov Yu. V., Glebov A. N., “Priblizhënnye algoritmy resheniya zadachi o dvukh kommivoyazhërakh v polnom grafe s vesami rëber 1 i 2”, Diskret. analiz i issled. operatsii. Ser. 2, 14:2 (2007), 41–61 | MR

[3] Glebov A. N., Zambalaeva D. Zh., “Zadacha o dvukh kommivoyazhërakh na minimum v polnom grafe s razlichnymi vesovymi funktsiyami”, Diskret. analiz i issled. operatsii, 18:4 (2011), 17–48

[4] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982, 416 pp. | MR

[5] Serdyukov A. I., “Algoritm s otsenkoi dlya zadachi kommivoyazhëra na maksimum”, Upravlyaemye sistemy, 25, 1984, 80–86 | MR | Zbl

[6] Baburin A. E., Croce F. D., Gimadi E. Kh., Glazkov Y. V., Paschos V. Th., “Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2”, Discrete Appl. Math., 157:9 (2009), 1988–1992 | DOI | MR | Zbl

[7] De Kort J. B. J. M., “A branch and bound algorithm for symmetric 2-peripatetic salesman problems”, Eur. J. Oper. Res., 10:2 (1993), 229–243 | DOI | MR | Zbl

[8] Gabow H. N., “An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems”, Proc. 15th Ann. ACM Symp. Theory of Computing (Boston, April 25–27, 1983), ACM Press, New York, 1983, 448–456

[9] Glebov A. N., Gordeeva A. V., Zambalaeva D. Zh., “7/5-Approximation algorithm for a 2-peripatetic salesman problem on minimum with different weight functions valued 1 and 2”, Discrete Appl. Math. (to appear)

[10] Gutin G., Punnen A. P., The traveling salesman problem and its variations, Kluwer Acad. Publ., Boston–London–Dordrecht, 2002, 830 pp. | MR

[11] Krarup J., “The peripatetic salesman and some related unsolved problems”, Combinatorial programming: methods and applications, Proc. NATO Advanced Study Inst. (Versailles, 1974), Kluwer Acad. Publ., Reidel–Dordrecht, 1975, 173–178 | MR

[12] Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G., Shmoys D. B., The traveling salesman problem: a guided tour of combinatorial optimization, Wiley, Chichester, 1985, 463 pp. | MR | Zbl

[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