Please use this identifier to cite or link to this item:
|Type:||Artigo de periódico|
|Title:||Approximation schemes for knapsack problems with shelf divisions|
|Abstract:||Given a knapsack of size K, non-negative values d and Delta, and a set S of iterns, each item e epsilon S with size s(e) and value v(e), we define a shelf as a subset of items packed inside a bin with total items size at most Delta. Two subsequent shelves must be separated by a shelf divisor of size d. The size of a shelf is the total size of its iterns plus the size of the shelf divisor. The SHELF-KNAPSACK Problem (SK) is to find a subset S' subset of S partitioned into shelves with total shelves size at most K and maximum value. The CLASS CONSTRAINED SHELF KNAPSACK (CCSK) is a generalization of the problem SK, where each item in S has a class and each shelf in the solution must have only items of the same class. We present approximation schemes for the SK and the CCSK problems. To our knowledge, these are the first approximation results where shelves of non-null size are used in knapsack problems. (c) 2005 Elsevier B.V. All rights reserved.|
|Editor:||Elsevier Science Bv|
|Appears in Collections:||Unicamp - Artigos e Outros Documentos|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.