Geodesic
On $m$-capacitated peripatetic salesman problem
Diskretnyj analiz i issledovanie operacij, Tome 20 (2013) no. 5, pp. 13-30.

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

We consider a particular case of the problem of finding $m$ Hamiltonian cycles with capacity restrictions on edges usage ($m$-Capacitated Peripatetic Salesman Problem, $m$-$\mathrm{CPSP}$): the $2$-CPSP on minimum and maximum with edge weights from an integer segment $\{1,q\}$. The edges capacities are independent identically distributed random variables which assume $2$ with probability $p$ and $1$ with probability $1-p$. Polynomial algorithms for $2$-$\mathrm{CPSP_{min}}$ and $2$-$\mathrm{CPSP_{max}}$ with guarantee approximation ratio in average for all possible inputs are presented. In the case when edge weights are $1$ and $2$, the presented algorithms have approximation ratio $(19-5p)/12$ and $(25+7p)/36$ for the $2$-$\mathrm{CPSP_{min}}$ and the $2$-$\mathrm{CPSP_{max}}$ correspondingly. Ill. 17, bibliogr. 20.
Keywords: travelling salesman problem, $m$-peripatetic salesman problem, approximation algorithm, edge-disjoint Hamiltonian cycle, guarantee approximation ratio. 
@article{DA_2013_20_5_a1,
     author = {E. Kh. Gimadi and A. M. Istomin and I. A. Rykov},
     title = {On $m$-capacitated peripatetic salesman problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {13--30},
     publisher = {mathdoc},
     volume = {20},
     number = {5},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2013_20_5_a1/}
}
TY  - JOUR
AU  - E. Kh. Gimadi
AU  - A. M. Istomin
AU  - I. A. Rykov
TI  - On $m$-capacitated peripatetic salesman problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2013
SP  - 13
EP  - 30
VL  - 20
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2013_20_5_a1/
LA  - ru
ID  - DA_2013_20_5_a1
ER  - 
%0 Journal Article
%A E. Kh. Gimadi
%A A. M. Istomin
%A I. A. Rykov
%T On $m$-capacitated peripatetic salesman problem
%J Diskretnyj analiz i issledovanie operacij
%D 2013
%P 13-30
%V 20
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2013_20_5_a1/
%G ru
%F DA_2013_20_5_a1
E. Kh. Gimadi; A. M. Istomin; I. A. Rykov. On $m$-capacitated peripatetic salesman problem. Diskretnyj analiz i issledovanie operacij, Tome 20 (2013) no. 5, pp. 13-30. http://geodesic.mathdoc.fr/item/DA_2013_20_5_a1/

[1] Ageev A. A., Pyatkin A. V., “Priblizhënnyi algoritm resheniya metricheskoi zadachi o dvukh kommivoyazhërakh s otsenkoi tochnosti 2”, Diskret. analiz i issled. operatsii, 16:4 (2009), 3–20 | MR | Zbl

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

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

[4] 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 | Zbl

[5] Gimadi E. Kh., Ivonina E. V., “Priblizhënnye algoritmy resheniya zadachi o dvukh kommivoyazhërakh na maksimum”, Diskret. analiz i issled. operatsii, 19:1 (2012), 17–32 | MR

[6] Glebov A. N., Zambalaeva D. Zh., “Priblizhënnyi algoritm resheniya zadachi o dvukh kommivoyazhërakh na minimum s razlichnymi vesovymi funktsiyami”, Diskret. analiz i issled. operatsii, 18:5 (2011), 11–37 | MR | Zbl

[7] Glebov A. N., Zambalaeva D. Zh., “Polinomialnyi algoritm s otsenkoi tochnosti 7/9 dlya zadachi o dvukh kommivoyazhërakh na maksimum”, Diskret. analiz i issled. operatsii, 18:4 (2011), 17–48 | MR | Zbl

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

[9] Baburin A. E., Della Croce F., Gimadi E. K., Glazkov Yu. V., Paschos V. Th., “Approximation algorithms for the 2-PSP with edge weights 1 and 2”, Discrete Appl. Math., 157:9 (2009), 1988–1992 | DOI | MR | Zbl

[10] Berman P., Karpinski M., “8/7-Approximation algorithm for (1,2)-TSP”, Proc. 17th Annual ACM-SIAM Symp. Discrete Algorithm, SODA' 06 (Miami, January, 2006), ACM, New York, 2006, 641–648 | DOI | MR | Zbl

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

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

[13] Della Croce F., Paschos V. Th., Wolfler Calvo R., “Approximating the 2-peripatetic traveling salesman problem”, 7th Workshop Modeling and Algorithms for Planning and Scheduling Problems, MAPSP 2005 (Siena, Italy, June 6–10, 2005), Springer-Verl., Berlin, 2005, 114–116

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

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

[16] Duchenne É., Laporte G., Semet F., “The undirected $m$-capacitated peripatetic salesman problem”, Eur. J. Oper. Res., 223:3 (2012), 637–643 | DOI | MR

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

[18] Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G., Shmoys D. B. (eds.), The traveling salesman problem: a guided tour of combinatorial optimization, John Wiley Sons, Chichester–New York–Brisbane–Toronto–Singapore, 1985, 463 pp. | MR | Zbl

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

[20] Roskind J., Tarjan R. E., “A note on finding minimum-cost edge-disjoint spanning trees”, Math. Oper. Res., 10:4 (1985), 701–708 | DOI | MR | Zbl