Please use this identifier to cite or link to this item:
Type: Artigo de periódico
Title: Two Dimensional Knapsack With Unloading Constraints
Author: Da Silveira J.L.M.
Xavier E.C.
Miyazawa F.K.
Abstract: n this paper we present approximation algorithms for the two dimensional knapsack problem with unloading constraints. In this problem, we have a bin B of width and height 1, and a list L with n items of C different classes, each item ai with height h(av), width w(ai), profit p(ai) and class c(ai). We have to pack a subset of the items of L into B, without rotations or overlaps, maximizing the total profit of packed items. In our problem the right side of the bin corresponds to the entry and leaving place of items. The class value of each item is an integer that indicates the order in which items must be unloaded from the bin. The generated packing must satisfy the unloading constraints: while removing one item, other items of higher classes can not block the way out of the item. We present a (4+∈)-approximation algorithm to this problem, a (3+∈)-approximation algorithm for the special case where profits are proportional to the items area, and a (3+∈)-approximation for the case in which the items are squares. © 2011 Elsevier B.V.
Rights: fechado
Identifier DOI: 10.1016/j.endm.2011.05.046
Date Issue: 2011
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File SizeFormat 
2-s2.0-80053068025.pdf166.82 kBAdobe PDFView/Open

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