Approximation Schemes for the Generalized Traveling Salesman Problem

M. Yu. Khachai   ; E. D. Neznakhina

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 22 (2016) no. 3, pp. 283-292

Résumé

The generalized traveling salesman problem (GTSP) is defined by a weighted graph $G=(V,E,w)$ and a partition of its vertex set into $k$ disjoint clusters $V=V_1\cup\ldots\cup V_k$. It is required to find a minimum-weight cycle that contains exactly one vertex of each cluster. We consider a geometric setting of the problem (we call it EGTSP-$k$-GC), in which the vertices of the graph are points in a plane, the weight function corresponds to the euclidian distances between the points, and the partition into clusters is specified implicitly by means of a regular integer grid with step 1. In this setting, a cluster is a subset of vertices lying in the same cell of the grid; the arising ambiguity is resolved arbitrarily. Even in this special setting, the GTSP remains intractable, generalizing in a natural way the classical planar Euclidean TSP. Recently, a $(1.5+8\sqrt2+\varepsilon)$-approximation algorithm with complexity depending polynomially both on the number of vertices $n$ and on the number of clusters $k$ has been constructed for this problem. We propose three approximation algorithms for the same problem. For any fixed $k$, all the schemes are PTAS and the complexity of the first two is linear in the number of nodes. Furthermore, the complexity of the first two schemes remains polynomial for $k=O(\log n)$, whereas the third scheme is polynomial for $k=n-O(\log n)$.

Détail

Keywords: generalized traveling salesman problem, NP-hard problem, polynomial-time approximation scheme.

Bibliographie

[1] Sesekin A.N., Chentsov A.A., Chentsov A.G., Zadachi marshrutizatsii peremeschenii, Lan, SPb., 2011, 256 pp.

[2] Arkin E.M., Hassin R., “Approximation algorithms for the geometric covering salesman problem”, Discrete Appl. Math., 55:3 (1994), 197–218 | 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] B. Bhattacharya, A. Custic, A. RafieyA, A. Rafiey, V. Sokol, “Approximation algorithms for generalized MST and TSP in grid clusters”, Combinatorial Optimization and Applications, 9th Internat. Conf. (COCOA 2015), Proc., LNCS, 9486, Springer International Publ., Cham, 2015, 110–125 | MR | Zbl

[5] Bontoux B., Artigues C., Feillet D., “A memetic algorithm with a large neighborhood crossover operator for the generalized traveling salesman problem”, Computers Oper. Res., 37:11 (2010), 1844–1852 | DOI | MR | Zbl

[6] Chentsov A.G., Khachai M.Yu., Khachai D.M., “Tochnyi algoritm s lineinoi trudoemkostyu dlya odnoi zadachi obkhoda megapolisov”, Tr. In-ta matematiki i mekhaniki UrO RAN, 21:3 (2015), 309–317 | MR

[7] Christofides N., Worst-case analysis of a new heuristic for the traveling salesman problem, Tech. report AD-A025 602, Carnegie-Mellon University, Pittsburgh, 1976, 11 pp.

[8] Dror M., Orlin J., “Combinatorial optimization with explicit delineation of the ground set by a collection of subsets”, SIAM J. Discrete Math., 21:4 (2008), 1019–1034 | DOI | MR

[9] Dumitrescu A., Mitchell J.S. B., “Approximation algorithms for TSP with neighborhoods in the plane”, Proc. of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '01), SIAM, Philadelphia, 2001, 38–46 | MR | Zbl

[10] Dumitrescu A., Toth C.D., “The traveling salesman problem for lines, balls, and planes”, ACM Trans. Algorithms, 12:3 (2016), 43:1–43:29 | DOI | MR

[11] Feremans C., Grigoriev A., Sitters R., “The geometric generalized minimum spanning tree problem with grid clustering”, 4OR, 4:4 (2006), 319–329 | DOI | MR | Zbl

[12] Gutin G., Karapetyan D., “A memetic algorithm for the generalized traveling salesman problem”, Nat. Comput., 9:1 (2010), 47–60 | DOI | MR | Zbl

[13] Held M., Karp R.M., “A dynamic programming approach to sequencing problems”, J. Soc. Indust. Appl. Math., 10:1 (1962), 196–210 | DOI | MR | Zbl

[14] Henry-Labordere A., “The record balancing problem: a dynamic programming solution of a generalized traveling salesman problem”, Rev. Franc. Inform. Rech. Oper. 3, 1969, no. B–2, 43–49 | Zbl

[15] Jun-man K., Yi Z., “Application of an improved ant colony optimization on generalized traveling salesman problem”, Energy Procedia, 17:A (2012), 319–325 | DOI

[16] Laporte G., Mercure H., Nobert Y., “Generalized travelling salesman problem through n sets of nodes: the asymmetrical case”, Discrete Appl. Math., 18:2 (1987), 185–197 | DOI | MR | Zbl

[17] Mata C.S., Mitchell J.S.B., “Approximation algorithms for geometric tour and network design problems”, Proc. of the Eleventh Annual Symposium on Computational Geometry (SCG '95), ACM, N.Y., 1995, 360–369 | DOI

[18] Mitchell J.S.B., “A PTAS for TSP with neighborhoods among fat regions in the plane”, Proc. of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '07), Philadelphia, 2007, 11–18 | MR | Zbl

[19] Saksena J., “Mathematical model for scheduling clients through welfare agencies”, CORS J., 8 (1970), 185–200 | MR | Zbl

[20] Williamson D., Shmoys D., The design of approximation algorithms, Cambridge University Press, Cambridge, 2010, 500 pp.