کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
481818 | 1446186 | 2007 | 5 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: A note on the approximability of cutting stock problems A note on the approximability of cutting stock problems](/preview/png/481818.png)
Cutting stock problems and bin packing problems are basically the same problems. They differ essentially on the variability of the input items. In the first, we have a set of items, each item with a given multiplicity; in the second, we have simply a list of items (each of which we may assume to have multiplicity 1). Many approximation algorithms have been designed for packing problems; a natural question is whether some of these algorithms can be extended to cutting stock problems. We define the notion of “well-behaved” algorithms and show that well-behaved approximation algorithms for one, two and higher dimensional bin packing problems can be translated to approximation algorithms for cutting stock problems with the same approximation ratios.
Journal: European Journal of Operational Research - Volume 183, Issue 3, 16 December 2007, Pages 1328–1332