Geodesic
Polynomial algorithm with approximation ratio $7/9$ for maximum 2-PSP
Diskretnyj analiz i issledovanie operacij, Tome 18 (2011) no. 4, pp. 17-48.

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

We study a 2-peripatetic salesman problem on maximum which consists in finding two edge-disjoint Hamiltonian cycles of maximum total weight in a complete undirected graph. We present a cubic time approximation algorithm for this problem with guaranteed ratio $7/9$, the best known for today. Ill. 5, bibliogr. 14.
Keywords: traveling salesman problem, 2-peripatetic salesman problem, guaranteed approximation ratio.
Mots-clés : polynomial algorithm 
@article{DA_2011_18_4_a1,
     author = {A. N. Glebov and D. Zh. Zambalayeva},
     title = {Polynomial algorithm with approximation ratio $7/9$ for maximum {2-PSP}},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {17--48},
     publisher = {mathdoc},
     volume = {18},
     number = {4},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2011_18_4_a1/}
}
TY  - JOUR
AU  - A. N. Glebov
AU  - D. Zh. Zambalayeva
TI  - Polynomial algorithm with approximation ratio $7/9$ for maximum 2-PSP
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2011
SP  - 17
EP  - 48
VL  - 18
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2011_18_4_a1/
LA  - ru
ID  - DA_2011_18_4_a1
ER  - 
%0 Journal Article
%A A. N. Glebov
%A D. Zh. Zambalayeva
%T Polynomial algorithm with approximation ratio $7/9$ for maximum 2-PSP
%J Diskretnyj analiz i issledovanie operacij
%D 2011
%P 17-48
%V 18
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2011_18_4_a1/
%G ru
%F DA_2011_18_4_a1
A. N. Glebov; D. Zh. Zambalayeva. Polynomial algorithm with approximation ratio $7/9$ for maximum 2-PSP. Diskretnyj analiz i issledovanie operacij, Tome 18 (2011) no. 4, pp. 17-48. http://geodesic.mathdoc.fr/item/DA_2011_18_4_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] Serdyukov A. I., “Algoritm s otsenkoi dlya zadachi kommivoyazhëra na maksimum”, Upravlyaemye sistemy. Sb. nauch. tr., 25, In-t matematiki SO AN SSSR, Novosibirsk, 1984, 80–86 | MR

[4] Chen Z.-Z., Okamoto Y., Wang L., “Improved deterministic approximation algorithms for Max TSP”, Inf. Process. Lett., 95:2 (2005), 333–342 | DOI | MR | Zbl

[5] Chen Z.-Z., Wang L., “An improved randomized approximation algorithm for Max TSP”, J. Comb. Optim., 9:4 (2005), 401–432 | DOI | MR | Zbl

[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., “Upper 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 2-peripatetic salesman problems”, Europ. 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”, Europ. 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 Annu. ACM Symp. Theory of Comput. (Boston, April 25–27, 1983), ACM, New York, 1983, 448–456

[12] Hassin R., Rubinstein S., “Better approximations for max TSP”, Inf. Process. Lett., 75:4 (2000), 181–186 | DOI | MR | Zbl

[13] Krarup J., “The peripatetic salesman and some related unsolved problems”, Combinatorial programming: methods and applications, Proc. NATO Advanced Study Inst. (Versailles, 1974), NATO Advanced Study Inst. Ser., Ser. C: Math. and Phys. Sci., 19, Reidel, Dordrecht, 1975, 173–178 | MR

[14] van Zuylen A., “Multiplying pessimistic estimators: deterministic approximation of max TSP and maximum triangle packing”, Computing and Combinatorics, 16th Annu. Int. Conf. COCOON 2010 (Nha Trang, Vietnam, July 19–21, 2010), Lect. Notes Comput. Sci., 6196, 2010, 60–69 | Zbl