Solvability of the Generalized Traveling Salesman Problem in the class of quasi- and pseudopyramidal tours

M. Yu. Khachay   ; E. D. Neznakhina

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 23 (2017) no. 3, pp. 280-291

Résumé

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.

Détail

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

Bibliographie

[1] B. Bhattacharya, A. Custic, A. Rafiey, A. Rafiey, V. Sokol, “Approximation algorithms for generalized MST and TSP in grid clusters”, Combinatorial Optimization and Applications, Proc. 9th Internat. Conf. (COCOA 2015), Lecture Notes in Computer Science, 9486, Springer International Publ., Cham, 2015, 110–125 | DOI | MR | Zbl

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

[3] Arora S., “Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems”, J. ACM, 45:5 (1998), 753–782 | DOI | MR | Zbl

[4] Balas E., “New classes of efficiently solvable generalized traveling salesman problems”, Ann. Oper. Res., 86 (1999), 529–558 | DOI | MR | Zbl

[5] Chentsov A., Khachay M., Khachay D., “Linear time algorithm for precedence constrained asymmetric generalized traveling salesman problem”, IFAC-PapersOnLine, 49:12 (2016), 651–655 | DOI

[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, Acad. Press, Orlando, 1976, 441 | MR

[7] Cygan M. et al, Parameterized Algorithms, Springer, Cham; Heidelberg; New York; Dordrecht; London, 2015, 613 pp. | DOI | Zbl

[8] Enomoto H., Oda Y., Ota K., “Pyramidal tours with step-backs and the asymmetric traveling salesman problem”, Discrete Appl. Math., 87:1–3 (1998), 57-65 | DOI | MR | Zbl

[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), 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) (Dagstuhl, Germany, 2016), v. 55, eds. eds. I. Chatzigiannakis, M. Mitzenmacher, Y. Rabani, D. Sangiorgi, 2016, 5:1–5:14 | MR

[10] Fischetti M., Gonzalez J., Toth P., “A branch-and-cut algorithm for the symmetric generalized traveling salesman problem”, Operations Research, 45:3 (1997), 378–394 | DOI | MR | Zbl

[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., 93:1 (2016), 117–120 | DOI | MR | Zbl

[12] Gutin G., Punnen A. P., The traveling salesman problem and its variations, Springer, Boston, 2007, 830 pp. | DOI | MR | Zbl

[13] Khachay M., Neznakhina K., “Approximability of the minimum-weight k-size cycle cover problem”, J. Glob. Optim., 66:1 (2016), 65–82 | DOI | MR | Zbl

[14] Khachay M., Neznakhina K., “Towards a PTAS for the generalized TSP in grid clusters”, AIP Conf. Proceedings, v. 1776, 2016, 050003 | DOI

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

[16] Oda Y., “An asymmetric analogue of van der Veen conditions and the traveling salesman problem”, Discrete Appl. Math., 109:3 (2001), 279–292 | DOI | MR | Zbl

[17] Oda Y., Ota K., “Algorithmic aspects of pyramidal tours with restricted jump-backs”, Interdiscip. Inform. Sci., 7:1 (2001), 123–133 | DOI | MR | Zbl

[18] Papadimitriou C., “Euclidean TSP is NP-complete”, Theoret. Comput. Sci., 4:3 (1977), 237–244 | DOI | MR | Zbl

[19] Sahni S., Gonzales T., “P-complete approximation problems”, J. ACM, 23:3 (1976), 555–565 | DOI | MR | Zbl

[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., 40:3 (1998), 496–546 | DOI | MR | Zbl