Polynomial algorithms for a problem of guillotine cutting a cuboid into two small cuboids

Автор: Arslanov Marat Zufarovich

Журнал: Проблемы информатики @problem-info

Рубрика: Теоретическая информатика

Статья в выпуске: 4 (25), 2014 года.

Бесплатный доступ

In the paper a problem of guillotine cutting a cuboid (cuboid means here always a rectangular box) into two cuboids is considered. The small cuboids can not be rotated. The question is whether there exists a cutting pattern with given numbers of occurrences of both cuboids. A polynomial time algorithm for constructing the convex hull of the set of feasible solutions to this problem is suggested.

Polynomial algorithms, 3d guillotine cutting, knapsack polygon, convex hull

Короткий адрес: https://sciup.org/14320257

IDR: 14320257

Список литературы Polynomial algorithms for a problem of guillotine cutting a cuboid into two small cuboids

  • Dyckhoff H. A typology of cutting and packing problems//European Journal of Operational Research. 1990. N 44. P. 145-159.
  • The Open Problems Project . http://cs.smith.edu/orourke/TOPP/. A project to record open problems of interest to researchers in computational geometry and related fields. 2011.
  • Tarnowski A. G., Terno J., Scheithauer G. A Polynomial Time Algorithm for the Guillotine Pallet Loading Problem//INFOR. 1994. N 32. P. 275-287.
  • Arslanov M. Z. Continued fractions in optimal cutting a rectangular sheet into equal small rectangles//European Journal of Operational Research. 2000. N 125. P. 239-248.
  • Arslanov M. Z. A polynomial algorithm for one problem of guillotine cutting.//Operations Research Letters. 2007. N 35. P. 636-644.
  • Girlich E., Tarnowski A. G. On polynomial solvability of two multiprocessor scheduling problems//Mathematical Methods of Operations Research. 1999. N 50. P. 27-51.
  • Rockafellar R. T. Convex Analysis. Princeton. 1971.
  • Harvey W. Computing Two-dimensional Integer Hulls//SIAM Journal on Computing. 1999. N 28. P. 2285-2299.
  • Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms, Second Edition. The MIT Press. 2001.
Еще
Статья научная