Program equivalence and context-free grammars
Barry K. Rosen
SWAT 1972
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.
Barry K. Rosen
SWAT 1972
Pavel Klavík, A. Cristiano I. Malossi, et al.
Philos. Trans. R. Soc. A
Paul G. Comba
Journal of the ACM
Anurag Ajay, Seungwook Han, et al.
NeurIPS 2023