Hagen Soltau, Lidia Mangu, et al.
ASRU 2011
In the generalized traveling-salesman problem (GTSP), we are given a set of cities that are grouped into possibly intersecting clusters. The objective is to find a closed path of minimum cost that visits at least one city in each cluster. Given an instance G of the GTSP, we first transform G into another instance G′ of the GTSP in which all the clusters are nonintersecting, and then transform G′ into an instance G″ of the standard traveling-salesman problem (TSP). We show that any feasible solution of the TSP instance G″ can be transformed into a feasible solution of the GTSP instance G of no greater cost, and that any optimal solution of the TSP instance G″ can be transformed into an optimal solution of the GTSP instance G. © 1993.
Hagen Soltau, Lidia Mangu, et al.
ASRU 2011
Zhikun Yuen, Paula Branco, et al.
DSAA 2023
Kenneth L. Clarkson, Elad Hazan, et al.
Journal of the ACM
Gaku Yamamoto, Hideki Tai, et al.
AAMAS 2008