М.Ю. Хачай, Е.Д.Незнахина.  Разрешимость обобщенной задачи коммивояжера в классе квази- и псевдопирамидальных маршрутов ... С. 280-291.

УДК 519.16 + 519.85

MSC: 90C27, 90C59, 90B06

DOI: 10.21538/0134-4889-2017-23-3-280-291

Полная версия статьи

Исследования поддержаны Российским научным фондом, грант 14-11-00109.

В работе изучается  общая постановка обобщенной задачи коммивояжера (GTSP), в которой требуется построить кратчайший циклический маршрут, посещающий каждый элемент фиксированного разбиения множества вершин  заданного взвешенного графа (именуемый кластером или мегаполисом) в единственной вершине. Обобщив классическое понятие пирамидального маршрута и введя в рассмотрение квази- и псевдопирамидальные маршруты для задачи GTSP, мы показали, что  оптимальный $l$-квазипирамидальный и $l$-псевдопирамидальный маршруты в произвольной постановке задачи на $n$ вершинах и $k$ кластерах могут быть построены за время $O(4^l n^3)$ и $O(2^lk^{l+4}n^3)$ соответственно. Как следствие показано, что задача GTSP принадлежит классу FPT относительно параметризаций, задаваемых такими типами маршрутов. Кроме того, обоснована полиномиальная разрешимость геометрического подкласса задачи, известного в литературе как GTSP-GC, произвольная постановка которого стеснена дополнительным ограничением $H\leq 2$ на высоту решетки, определяющей кластеры.

Ключевые слова: обобщенная задача коммивояжера (GTSP), полиномиально разрешимый подкласс, квазипирамидальный маршрут, псевдопирамидальный маршрут.

СПИСОК ЛИТЕРАТУРЫ

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

2.   Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2 / A. Baburin, F. Della Croce, E. K. Gimadi, Y. V. Glazkov, V. T. Paschos // Discrete Appl. Math. 2009. Vol. 157, no. 9. P. 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. P. 753–782.

4.   Balas E. New classes of efficiently solvable generalized traveling salesman problems // Ann. Oper. Res. 1999. Vol. 86. P. 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. P. 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. P. 441.

7.   Cygan M. et al. 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. P. 57–65.

9.   Fine-grained complexity analysis of two classic TSP variants / M. de Berg, K. Buchin, B. M. P. Jansen, G. Woeginger // Leibniz International Proceedings in Informatics (LIPIcs). 2016. Vol. 55. P. 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. P. 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. P. 117–120. doi: 10.1134/S1064562416010233 .

12.   Gutin G., Punnen A. P. The traveling salesman problem and its variations. Boston: Springer, 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. P. 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. Proceedings. 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. P. 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. P. 123–133. doi: 10.4036/iis.2001.123 .

18.   Papadimitriou C. Euclidean TSP is NP-complete // Theoret. Comput. Sci. 1977. Vol. 4, no. 3. P. 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. P. 555–565. doi: 10.1145/321958.321975 .

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

Поступила 29.05.17

Хачай Михаил Юрьевич 
доктор физ.-мат. наук, проф. РАН, зав. отделом
Инcтитут математики и механики им. Н.Н.Красовского УрО РАН,
Уральский федеральный университет, г. Екатеринбург
Омский государственный технический университет, г. Омск
e-mail: mkhachay@imm.uran.ru

Незнахина Екатерина Дмитриевна
аспирант, науч. сотрудник
Инcтитут математики и механики им. Н.Н.Красовского УрО РАН,
Уральский федеральный университет,
г. Екатеринбург
e-mail: eneznakhina@yandex.ru

English

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

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