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.