Abstract
In this paper, we introduce the notion of l-quasi-pyramidal and l-pseudo-pyramidal tours extending the classic notion of pyramidal tours to the case of the Generalized Traveling Salesman Problem (GTSP). We show that, for the instance of GTSP on n cities and k clusters with arbitrary weights, l-quasi-pyramidal and l-pseudo-pyramidal optimal tours can be found in time \(O(4^ln^3)\) and \(O(2^lk^{l+4}n^3)\), respectively. Consequently, we show that, in the most general setting, GTSP belongs to FPT for parametrizations induced by these special kinds of tours. Also, we describe a non-trivial polynomially solvable subclass of GTSP, for which the existence of l-quasi-pyramidal optimal tour (for some fixed value of l) is proved.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
In this paper, we restrict ourselves to the case of undirected graphs. Nevertheless, the analogous argument can be provided to the case of digraphs and asymmetric weighting functions w.
References
Arora, S.: Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems. J. ACM 45, 753–783 (1998)
Baburin, A., Della Croce, F., Gimadi, E.K., Glazkov, Y.V., Paschos, V.T.: Approximation algorithms for the 2-Peripatetic salesman problem with edge weights 1 and 2. Discrete Appl. Math. 157(9), 1988–1992 (2009)
Baki, M.F.: A new asymmetric pyramidally solvable class of the traveling salesman problem. Oper. Res. Lett. 34(6), 613–620 (2006). http://www.sciencedirect.com/science/article/pii/S0167637706000022
Balas, E.: New classes of efficiently solvable generalized Traveling Salesman Problems. Ann. Oper. Res. 86, 529–558 (1999)
Balas, E., Simonetti, N.: Linear time dynamic-programming algorithms for new classes of restricted TSPs: a computational study. INFORMS J. Comput. 13(1), 56–75 (2001). https://doi.org/10.1287/ijoc.13.1.56.9748
de Berg, M., Buchin, K., Jansen, B.M.P., Woeginger, G.: Fine-grained complexity analysis of two classic TSP Variants. In: Chatzigiannakis, I., Mitzenmacher, M., Rabani, Y., Sangiorgi, D. (eds.) 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), vol. 55, pp. 5:1–5:14. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2016). http://drops.dagstuhl.de/opus/volltexte/2016/6277
Burkard, R.E., Glazkov, Y.V.: On the traveling salesman problem with a relaxed monge matrix. Inform. Process. Lett. 67(5), 231–237 (1998). http://www.sciencedirect.com/science/article/pii/S0020019098001197
Burkard, R.E., Deineko, V.G., van Dal, R., van der Veen, J.A.A., Woeginger, G.J.: Well-solvable special cases of the traveling salesman problem: a survey. SIAM Rev. 40(3), 496–546 (1998)
Chentsov, A.G., Khachai, M.Y., Khachai, D.M.: An exact algorithm with linear complexity for a problem of visiting megalopolises. Proc. Steklov Ins. Math. 295(1), 38–46 (2016). https://doi.org/10.1134/S0081543816090054
Christofides, N.: Worst-case analysis of a new heuristic for the Traveling Salesman Problem. In: Symposium on New Directions and Recent Results in Algorithms and Complexity, p. 441 (1975)
Enomoto, H., Oda, Y., Ota, K.: Pyramidal tours with step-backs and the asymmetric Traveling Salesman Problem. Discrete Appl. Math. 87(1–3), 57–65 (1998)
Gimadi, E.K., Glazkov, Y., Tsidulko, O.Y.: Probabilistic analysis of an algorithm for the m-planar 3-index assignment problem on single-cycle permutations. J. Appl. Ind. Math. 8(2), 208–217 (2014)
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), 117–120 (2016)
Gutin, G., Punnen, A.P.: The Traveling Salesman Problem and Its Variations. Springer, Boston (2007)
Khachai, M., Neznakhina, E.: Approximability of the problem about a minimum-weight cycle cover of a graph. Doklady Math. 91(2), 240–245 (2015)
Khachay, M., Neznakhina, K.: Approximability of the minimum-weight k-Size cycle cover problem. J. Glob. Optim. 66(1), 65–82 (2016). https://doi.org/10.1007/s10898-015-0391-3
Khachay, M., Neznakhina, K.: Towards a PTAS for the generalized TSP in grid clusters. AIP Conf. Proc. 1776(1), 050003 (2016). https://doi.org/10.1063/1.4965324
Klyaus, P.: Generation of testproblems for the Traveling Salesman Problem. Preprint Inst. Mat. Akad. Nauk. BSSR (16) (1976). (in Russian)
Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B.: The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley Series in Discrete Mathematics & Optimization. Wiley, Chichester (1985)
Oda, Y., Ota, K.: Algorithmic aspects of pyramidal tours with restricted jump-backs. Interdisc. Inform. Sci. 7(1), 123–133 (2001)
Pardalos, P., Du, D., Graham, R.: Handbook of Combinatorial Optimization. Springer, New York (2013). https://doi.org/10.1007/978-1-4419-7997-1
Sahni, S., Gonzales, T.: P-complete approximation problems. J. ACM 23, 555–565 (1976)
Acknowledgements
This research was supported by Russian Science Foundation, project no. 14-11-00109.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Khachay, M., Neznakhina, K. (2017). Generalized Pyramidal Tours for the Generalized Traveling Salesman Problem. In: Gao, X., Du, H., Han, M. (eds) Combinatorial Optimization and Applications. COCOA 2017. Lecture Notes in Computer Science(), vol 10627. Springer, Cham. https://doi.org/10.1007/978-3-319-71150-8_23
Download citation
DOI: https://doi.org/10.1007/978-3-319-71150-8_23
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-71149-2
Online ISBN: 978-3-319-71150-8
eBook Packages: Computer ScienceComputer Science (R0)