Please use this identifier to cite or link to this item:
|Type:||Artigo de periódico|
|Title:||A note on the approximability of cutting stock problems|
|Abstract:||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. (c) 2006 Elsevier B.V. All rights reserved.|
|Editor:||Elsevier Science Bv|
|Appears in Collections:||Artigos e Materiais de Revistas Científicas - Unicamp|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.