No label defined (Q3973407)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 16721
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 16721 |
Statements
26 June 1992
0 references
rotations
0 references
traveling salesman
0 references
0.7763169407844543
0 references
0.7646350860595703
0 references
0.7591588497161865
0 references
0.7579603791236877
0 references
[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.
0 references