Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/54830
Type: Artigo de periódico
Title: Approximation schemes for knapsack problems with shelf divisions
Author: Xavier, EC
Miyazawa, FK
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.
Subject: approximate algorithms
approximation schemes
knapsack problem
shelf packing
Country: Holanda
Editor: Elsevier Science Bv
Rights: fechado
Identifier DOI: 10.1016/j.tcs.2005.10.036
Date Issue: 2006
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
WOS000235826900006.pdf234.61 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.