Artículos de revistas
A note on the approximability of cutting stock problems
Registro en:
European Journal Of Operational Research. Elsevier Science Bv, v. 183, n. 3, n. 1328, n. 1332, 2007.
0377-2217
WOS:000248590100029
10.1016/j.ejor.2005.09.053
Autor
Cintra, GF
Miyazawa, FK
Wakabayashi, Y
Xavier, EC
Institución
Resumen
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. 183 3 1328 1332