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

      0 references
      0 references
      26 June 1992
      0 references
      rotations
      0 references
      traveling salesman
      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

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references