Geodesic
$2/3$-approximation algorithm for the maximization version of the asymmetric two peripatetic salesman problem
Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 6, pp. 11-20.

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

We present a polynomial approximation algorithm for the maximization version of the asymmetric two peripatetic salesman problem which consists in finding two edge-disjoint Hamiltonian circuits of maximum total weight in a complete weighted digraph. The algorithm guarantees an approximation ratio of $2/3$ in cubic running time. Ill. 5, bibliogr. 7.
Keywords: traveling salesman problem, peripatetic salesman problem, guaranteed ratio, directed graph.
Mots-clés : polynomial algorithm 
@article{DA_2014_21_6_a1,
     author = {A. N. Glebov and D. Zh. Zambalaeva and A. A. Skretneva},
     title = {$2/3$-approximation algorithm for the maximization version of the asymmetric two peripatetic salesman problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {11--20},
     publisher = {mathdoc},
     volume = {21},
     number = {6},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2014_21_6_a1/}
}
TY  - JOUR
AU  - A. N. Glebov
AU  - D. Zh. Zambalaeva
AU  - A. A. Skretneva
TI  - $2/3$-approximation algorithm for the maximization version of the asymmetric two peripatetic salesman problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2014
SP  - 11
EP  - 20
VL  - 21
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2014_21_6_a1/
LA  - ru
ID  - DA_2014_21_6_a1
ER  - 
%0 Journal Article
%A A. N. Glebov
%A D. Zh. Zambalaeva
%A A. A. Skretneva
%T $2/3$-approximation algorithm for the maximization version of the asymmetric two peripatetic salesman problem
%J Diskretnyj analiz i issledovanie operacij
%D 2014
%P 11-20
%V 21
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2014_21_6_a1/
%G ru
%F DA_2014_21_6_a1
A. N. Glebov; D. Zh. Zambalaeva; A. A. Skretneva. $2/3$-approximation algorithm for the maximization version of the asymmetric two peripatetic salesman problem. Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 6, pp. 11-20. http://geodesic.mathdoc.fr/item/DA_2014_21_6_a1/

[1] Glebov A. N., Zambalaeva D. Zh., “A polynomial algorithm with approximation ratio 7/9 for the maximum two peripatetic salesmen problem”, J. Appl. Industr. Math., 6:1 (2012), 69–89 | DOI | MR | Zbl

[2] Kaplan H., Lewenstein M., Shafrir N., Sviridenko M., “Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs”, JACM, 52:4 (2005), 602–626 | DOI | MR

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

[4] De Kort J. B. J. M., “Upper bounds for the symmetric 2-peripatetic salesman problems”, Optimization, 23:4 (1992), 357–367 | DOI | MR | Zbl

[5] 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

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

[7] Paluch K., Mucha M., Madry A., “A 7/9-approximation algorithm for the maximum traveling salesman problem”, APPROX-RANDOM, Lecture Notes in Comput. Sci., 5687, 2009, 298–311 | MR | Zbl