Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/76486
Type: Artigo de periódico
Title: A NOTE ON A TWO DIMENSIONAL KNAPSACK PROBLEM WITH UNLOADING CONSTRAINTS
Author: da Silveira, JLM
Xavier, EC
Miyazawa, FK
Abstract: In this paper we address the two-dimensional knapsack problem with unloading constraints: we have a bin B, and a list L of n rectangular items, each item with a class value in {1, ... , C}. The problem is to pack a subset of L into B, maximizing the total profit of packed items, where the packing must satisfy the unloading constraint: while removing one item a, items with higher class values can not block a. We present a (4+epsilon)-approximation algorithm when the bin is a square. We also present (3+epsilon)-approximation algorithms for two special cases of this problem.
Subject: Knapsack problem
approximation algorithms
unloading/loading constraints
Country: França
Editor: Edp Sciences S A
Rights: aberto
Identifier DOI: 10.1051/ita/2013037
Date Issue: 2013
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
There are no files associated with this item.


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