On 2-Capacitated Peripatetic Salesman Problem with Different Weight Functions

E. Kh. Gimadi   ; A. M. Istomin   ; I. A. Rykov

Sibirskij žurnal čistoj i prikladnoj matematiki, Tome 14 (2014) no. 3, pp. 3-18

Résumé

We considered a particular case of a problem of finding $m$ Hamiltonian cycles with capacity restrictions on edges usage ($m$-Capacitated Peripatetic Salesman Problem, $m$-CPSP): the $2$-CPSP on minimum and maximum with edge weights from an integer segment $\{1,q\}$ with different weight functions. The edges capacities are independent identically distributed random variables, which is $2$ with probability $p$ and is $1$ with probability $(1-p)$. A polynomial algorithms for $2$-CPSP$_{\min}^d$ and $2$-CPSP$_{\max}^d$ with guarantee approximation ratio in average for all possible inputs was presented. In the case when edge weights are $1$ and $2$, the presented algorithms have approximation ratios $(19-5p)/12$ and $(25 + 7p)/36$ for the $2$-CPSP$_{\min}^d$ and the $2$-CPSP$_{\max}^d$ correspondingly.

Détail

Keywords: travelling salesman problem, $m$-peripatetic salesman problem, approximation algorithm, edge-disjoint Hamiltonian cycles, guarantee approximation ratio.

Bibliographie

[1] Garey M. R., Johnson D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Co., San Francisco, 1979

[2] E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, D. B. Shmoys (eds.), The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, Wiley, Chichester, 1985

[3] G. Gutin, A. P. Punnen (eds.), The Traveling Salesman Problem and its Variations, Kluwer Academic Publishers, Dordrecht–Boston–London, 2002

[4] Krarup J., “The Peripatetic Salesman and Some Related Unsolved Problems”, Combinatorial Programming: Methods and Applications, Proc. NATO Adv. Study Inst. (Versailles, 1974), 1975, 173–178

[5] De Kort J. B. J. M., “A Branch and Bound Algorithm for Symmetric 2-Peripatetic Salesman Problems”, European J. of Oper. Res., 10:2 (1993), 229–243 | DOI

[6] Duchenne É., Laporte G., Semet F., “The Undirected $m$-Capacitated Peripatetic Salesman Problem”, European J. of Oper. Res., 223:3 (2012), 637–643 | DOI

[7] Gimadi E. Kh., Istomin A. M., Rykov I. A., “On $m$-capacitated peripatetic salesman problem”, Diskretn. Anal. Issled. Oper., 20:5 (2013), 13–30 (in Russian)

[8] Papadimitriu C. H., Yannakakis M., “The Travelling Salesman Problem with Distance One and Two”, Math. Oper. Res., 18:1 (1993), 1–11 | DOI

[9] Gimadi E. Kh., Ivonina E. V., “Approximation algorithms for maximum-weight problem of two-peripatetic salesmen”, Diskretn. Anal. Issled. Oper., 19:1 (2012), 17–32 (in Russian)

[10] Ageev A. A., Baburin A. E., Gimadi E. Kh., “A polynomial algorithm with an accuracy estimate of 3/4 for finding two nonintersecting Hamiltonian cycles of maximum weight”, Diskretn. Anal. Issled. Oper. Ser. 1, 13:2 (2006), 11–20 (in Russian)

[11] Glebov A. N., Zambalayeva D. Zh., “Polynomial algorithm with approximation ratio 7/9 for maximum 2-PSP”, Diskretn. Anal. Issled. Oper., 18:4 (2011), 17–48 (in Russian)

[12] Baburin A. E., Gimadi E. Kh., Korkishko N. M., “Approximate algorithms for finding two edge-disjoint Hamiltonian cycles of minimal weight”, Diskretn. Anal. Issled. Oper. Ser. 2, 11:1 (2004), 11–25 (in Russian)

[13] Ageev A. A., Pyatkin A. V., “A 2-approximation algorithm for the metric 2-peripatetic salesman problem”, Diskretn. Anal. Issled. Oper., 16:4 (2009), 3–20 (in Russian)

[14] Della Croce F., Paschos V. Th., Wolfler Calvo R., “Approximating the 2-Peripatetic Traveling Salesman Problem”, 7$^\mathrm{th}$ Workshop on Modeling and Algorithms for Planning and Scheduling Problems, MAPSP 2005 (Siena, Italy, June 6–10, 2005), Springer, Berlin, 2005, 114–116

[15] Gimadi E. Kh., Glazkov Yu. V., Glebov A. N., “Approximation algorithms for solving the 2-peripatetic salesman problem on a complete graph with edge weights 1 and 2”, Diskretn. Anal. Issled. Oper. Ser. 2, 14:2 (2007), 41–60 (in Russian)

[16] Glebov A. N., Gordeeva A. V., Zambalayeva D. Zh., “7/5-approximation algorithm for 2-PSP on minimum with different weight functions”, Sib. Elektron. Mat. Izv., 8 (2011), 296–309 (in Russian)

[17] Glebov A. N., Zambalayeva D. Zh., “An approximation algorithm for the minimum 2-PSP with different weight functions valued 1 and 2”, Diskretn. Anal. Issled. Oper., 18:5 (2011), 11–37 (in Russian)