Solvable Classes of generalized Traveling Salesman Problems

	We consider the problem of disjoint packing of trapezoids of a given width h into a strip 
of the same width h so as to minimize the total length of the strip required. Various modifications
of the problem are considered by allowing various types of rotations of the trapezoids. When no
rotation is allowed, the problem belongs to the well known Gilmore-Gomory class of traveling 
salesman problems and hence can be solved in O(nlogn) time. When various types of rotations are 
allowed, we get different special cases of what we term "the generalized traveling salesman
problem". For each of these cases, an O(nlogn) time algorithm is developed. One of the algorithms
leads to a nontrivial generalization of the Gilmore-Gomory patching scheme. Some interesting 
applications of this new scheme are discussed.