Towards a PTAS for the generalized TSP in grid clusters / Khachay M., Neznakhina K. // AIP Conference Proceedings. - 2016. - V. 1776, l. .

ISSN:

0094243X

Type:

Conference Paper

Abstract:

The Generalized Traveling Salesman Problem (GTSP) is a combinatorial optimization problem, which is to find a minimum cost cycle visiting one point (city) from each cluster exactly.We consider a geometric case of this problem, where n nodes are given inside the integer grid (in the Euclidean plane), each grid cell is a unit square. Clusters are induced by cells 'populated' by nodes of the given instance. Even in this special setting, the GTSP remains intractable enclosing the classic Euclidean TSP on the plane. Recently, it was shown that the problem has (1:5+8√2+ϵ)-approximation algorithm with complexity bound depending on n and k polynomially, where k is the number of clusters. In this paper, we propose two approximation algorithms for the Euclidean GTSP on grid clusters. For any fixed k, both algorithms are PTAS. Time complexity of the first one remains polynomial for k = O(log n) while the second one is a PTAS, when k = n -O(log n).Grant: This research was supported by Russian Science Foundation, project no. 14-11-00109.

Author keywords:

Index keywords:

нет данных

DOI:

10.1063/1.4965324

Смотреть в Scopus:

https://www.scopus.com/inward/record.uri?eid=2-s2.0-84995484394&doi=10.1063%2f1.4965324&partnerID=40&md5=e3004fca320e6d413d5752f29c0234fa

Соавторы в МНС:

—

Другие поля

Поле	Значение
Art. No.	050003
Link	https://www.scopus.com/inward/record.uri?eid=2-s2.0-84995484394&doi=10.1063%2f1.4965324&partnerID=40&md5=e3004fca320e6d413d5752f29c0234fa
Affiliations	Krasovskii Institute of Mathematics and Mechanics, Ekaterinburg, Russian Federation; Ural Federal University, Ekaterinburg, Omsk, Russian Federation; State Technical University, Omsk, Russian Federation
References	Henry-Labordere, A., The record balancing problem: A dynamic programming solution of a generalized traveling salesman problem (1969) RIBO, B-2, pp. 736-743; Saksena, J., (1970) CORS Journal, 8, pp. 185-200; Bovet, J., Selective traveling salesman problem (1983) EURO VI Conference, , Papers presented at the, Vienna; Bontoux, B., Artigues, C., Feillet, D., (2010) Computers & Operations Research, 37, pp. 1844-1852; G. Gutin and D. Karapetyan, 9, 47-60 (2010); Jun-Man, K., Yi, Z., (2012) Energy Procedia, 17, pp. 319-325; Steiner, G., (1990) Annals of Operations Research, 26, pp. 103-123; Chentsov, A., Khachay, M., Khachay, D., (2016) Proceedings of the Steklov Institute of Mathematics, 294; Laporte, G., Mercure, H., Nobert, Y., (1987) Discrete Applied Mathematics, 18, pp. 185-197; Christofides, N., Worst-case analysis of a new heuristic for the traveling salesman problem (1975) Symposium on New Directions and Recent Results in Algorithms and Complexity, p. 441; Arora, S., (1998) Journal of the ACM, 45; Srivastava, S., Kumar, S., Garg, R., Sen, P., (1969) CORS Journal, 7, pp. 77-101; Laporte, G., Nobert, Y., (1983) Informatica, 21, pp. 61-75; Bhattacharya, B., Custic, A., Rafiey, A., Rafiey, A., Sokol, V., (2015) Combinatorial Optimization and Applications: 9th International Conference, COCOA 2015, Houston, TX, USA, December 18-20, 2015, Proceedings, pp. 110-125. , Springer International Publishing, Cham, Chap. Approximation Algorithms for Generalized MST and TSP in Grid Clusters; Held, M., Karp, R.M., A dynamic programming approach to sequencing problems (1961) Proceedings of the 1961 16th ACM National Meeting, ACM '61, pp. 71201-71204. , ACM, New York, NY, USA
Correspondence Address	Neznakhina, K.; Krasovskii Institute of Mathematics and MechanicsRussian Federation; email: eneznakhina@yandex.ru
Editors	Sergeyev Y.D.Mukhametzhanov M.S.Dell'Accio F.Mukhametzhanov M.S.Kvasov D.E.Sergeyev Y.D.Kvasov D.E.
Sponsors	Department of Computer Engineering, Modeling, Electronics and Systems Science of the University of Calabria;et al.;Institute of High Performance Computing and Networking of the National Research Council;International Association "Friends of the University of Calabria";Italian National Group for Scientific Computation of the National Institute for Advanced Mathematics "F. Severi";University of Calabria
Publisher	American Institute of Physics Inc.
Conference name	2nd International Conference on Numerical Computations: Theory and Algorithms, NUMTA 2016
Conference date	19 June 2016 through 25 June 2016
Conference code	124552
ISBN	9780735414389
Language of Original Document	English
Abbreviated Source Title	AIP Conf. Proc.
Source	Scopus