M.Yu. Khachai, E.D. Neznakhina. Solvability of the Generalized Traveling Salesman Problem in the class of quasi- and pseudopyramidal tours ... P. 280-291.

We consider the general setting of the Generalized Traveling Salesman Problem (GTSP), where, for a given weighted graph and a partition of its nodes into clusters (or megalopolises), it is required to find a cheapest cyclic tour visiting each cluster exactly once. Generalizing the classical notion of pyramidal tour, we introduce quasi- and pseudopyramidal tours for the GTSP and show that, for an arbitrary instance of the problem with $n$ nodes and $k$ clusters, optimal $l$-quasi-pyramidal and $l$-pseudopyramidal tours can be found in time $O(4^l n^3)$ and $O(2^lk^{l+4}n^3)$, respectively. As a consequence, we prove that the GTSP belongs to the class FTP with respect to parametrizations given by such types of routes. Furthermore, we establish the polynomial-time solvability of the geometric subclass of the problem known in the literature as GTSP-GC, where an arbitrary statement is subject to the additional constraint $H\le 2$ on the height of the grid defining the clusters.

Keywords: Generalized Traveling Salesman Problem (GTSP), polynomially solvable subclass, quasi-pyramidal tour, pseudopyramidal tour.

The paper was received by the Editorial Office on May 29, 2017.

Mikhail Yur’evich Khachai, Dr. Phys.-Math. Sci., Prof., Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620990 Russia; Ural Federal University, Yekaterinburg, 620002 Russia; Omsk State Technical University, Omsk, 644050 Russia, e-mail: mkhachay@imm.uran.ru

Ekaterina Dmitrievna Neznakhina, doctoral student, Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620990 Russia; Ural Federal University, Yekaterinburg, 620002 Russia,  e-mail: eneznakhina@yandex.ru


1.   Bhattacharya B., Д CustiДc A., Rafiey A., Rafiey A., Sokol V. Approximation algorithms for generalized MST and TSP in grid clusters. Combinatorial Optimization and Applications, Proc. 9th Internat. Conf. (COCOA 2015), Cham, Springer Internat. Publ., 2015, Ser. Lecture Notes in Computer Science, vol. 9486, pp. 110–125. doi: 10.1007/978-3-319-26626-8_9 .

2.   Baburin A., Della Croce F., GimadiE. K., Glazkov Y. V., Paschos V. T. Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2. Discrete Appl. Math., 2009, vol. 157,no. 9, pp. 1988–1992. doi: 10.1134/S1990478909010074 .

3.   Arora S. Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems. J. ACM, 1998, vol. 45, no. 5, pp. 753–782.

4.   Balas E. New classes of efficiently solvable generalized traveling salesman problems. Ann. Oper. Res., 1999, vol. 86, pp. 529–558.

5.   Chentsov A., Khachay M., Khachay D. Linear time algorithm for precedence constrained asymmetric generalized traveling salesman problem. IFAC-PapersOnLine, 2016, vol. 49, no. 12, pp. 651–655.
doi: 10.1016/j.ifacol.2016.07.767 .

6.   Christofides N. Worst-case analysis of a new heuristic for the traveling salesman problem. Algorithms and Complexity: New Directions and Recent Results, Proc. Symposium on New Directions and Recent Results in Algorithms and Complexity, ed. J.F. Traub, Orlando: Acad. Press., 1976, pp. 441.

7.   Cygan M., Fomin F.V., Kowalik L., Lokshtanov D., Marx D., Pilipczuk Marcin, Pilipczuk Michal, Saurabh S. Parameterized algorithms. Cham, Heidelberg, New York, Dordrecht, London, Springer, 2015,613 p. doi: 10.1007/978-3-319-21275-3 .

8.   Enomoto H., Oda Y., Ota K. Pyramidal tours with step-backs and the asymmetric traveling salesman problem. Discrete Appl. Math., 1998, vol. 87, no. 1–3, pp. 57–65.

9.   M. de Berg, K. Buchin, B. M. P. Jansen, G. Woeginger. Fine-grained complexity analysis of two classic TSP variants. Leibniz International Proceedings in Informatics (LIPIcs), 2016, vol. 55, pp. 5:1–5:14, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), eds. I. Chatzigiannakis, M. Mitzenmacher, Y. Rabani, D. Sangiorgi (Dagstuhl, Germany, 2016).
ISBN 978-3-95977-013-2 .

10.   Fischetti M., Gonzalez J., Toth P. A branch-and-cut algorithm for the symmetric generalized traveling salesman problem // Operations Research, 1997, vol. 45, no.3, pp. 378–394.

11.   Gimadi E. K., Rykov I. A. On the asymptotic optimality of a solution of the euclidean problem of covering a graph by m nonadjacent cycles of maximum total weight. Dokl. Math., 2016, vol. 93, no. 1,pp. 117–120. doi:10.1134/S1064562416010233 .

12.   Gutin G., Punnen A. P. The traveling salesman problem and its variations. Boston: Springer US, 2007, 830 p. doi: 10.1007/b101971 .

13.   Khachay M., Neznakhina K. Approximability of the minimum-weight k-size cycle cover problem. J. Glob. Optim., 2016, vol. 66, no. 1, pp. 65–82. doi:10.1007/s10898-015-0391-3 .

14.   Khachay M., Neznakhina K. Towards a PTAS for the generalized TSP in grid clusters. AIP Conf. Proc., 2016, vol. 1776, 050003. doi: 10.1063/1.4965324 .

15.   Klyaus P. Generation of testproblems for the traveling salesman problem. Preprint Inst. Mat. Akad. Nauk. BSSR. Minsk, 1976, no. 16 (in Russian).

16.   Oda Y. An asymmetric analogue of van der Veen conditions and the traveling salesman problem. Discrete Appl. Math., 2001, vol. 109, no. 3, pp. 279–292. doi: 10.1016/S0166-218X(00)00273-0 .

17.   Oda Y., Ota K. Algorithmic aspects of pyramidal tours with restricted jump-backs. Interdiscip. Inform. Sci., 2001, vol. 7, no. 1, pp. 123–133. doi: 10.4036/iis.2001.123 .

18.   Papadimitriou C. Euclidean TSP is NP-complete. Theoret. Comput. Sci., 1977, vol. 4, no. 3, pp. 237–244. doi: 10.1016/0304-3975(77)90012-3 .

19.   Sahni S., Gonzales T. P-complete approximation problems. J. ACM, 1976, vol. 23, no. 3, pp. 555–565. doi: 10.1145/321958.321975 .

20.   R. E. Burkard, V. G. Deineko, R. van Dal, J. A. A. van der Veen, G. J. Woeginger. Well-solvable special cases of the traveling salesman problem: A survey. SIAM Rev. Sept., 1998, vol. 40, no. 3,pp. 496–546.