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.
Статья научная
