scientific article; zbMATH DE number 16721
[For the entire collection see Zbl 0722.00003.] The generalized traveling salesman problem is to assign one of several states to each node and then find a tour of points so as to minimize the total cost of the tour. The cost of an edge is a function of the states chosen for its endpoints. The regular traveling salesman problem has just one state per node. In this paper, the authors examine the question of packing trapezoids of identical width into a strip of the same width. If no rotations are permitted, the problem is a specially structured traveling salesman problem, solvable by an algorithm of \textit{P. C. Gilmore} and \textit{R. E. Gomory} [Oper. Res. 12, 655-679 (1964)]. Rotations turn the problem into a generalized traveling salesman problem, where the states correspond to the rotation. If only horizontal rotations are permitted, the problem is similar to the first class. If rotations perpendicular to the strip are permitted, the problem is a generalization of the Gilmore and Gomory class, and can still be solved in \(O(m \log m)\) time. The case of vertical rotations is open.
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3973407)