Voir la notice de l'article provenant de la source Numdam
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 + ϵ)-approximation algorithm when the bin is a square. We also present (3 + ϵ)-approximation algorithms for two special cases of this problem.
@article{ITA_2013__47_4_315_0,
author = {Mois\'es da Silveira, Jefferson Luiz and Xavier, Eduardo Candido and Miyazawa, Fl\'avio Keidi},
title = {A note on a two dimensional knapsack problem with unloading constraints},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {315--324},
publisher = {EDP-Sciences},
volume = {47},
number = {4},
year = {2013},
doi = {10.1051/ita/2013037},
mrnumber = {3132294},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2013037/}
}
TY - JOUR AU - Moisés da Silveira, Jefferson Luiz AU - Xavier, Eduardo Candido AU - Miyazawa, Flávio Keidi TI - A note on a two dimensional knapsack problem with unloading constraints JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2013 SP - 315 EP - 324 VL - 47 IS - 4 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ita/2013037/ DO - 10.1051/ita/2013037 LA - en ID - ITA_2013__47_4_315_0 ER -
%0 Journal Article %A Moisés da Silveira, Jefferson Luiz %A Xavier, Eduardo Candido %A Miyazawa, Flávio Keidi %T A note on a two dimensional knapsack problem with unloading constraints %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2013 %P 315-324 %V 47 %N 4 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ita/2013037/ %R 10.1051/ita/2013037 %G en %F ITA_2013__47_4_315_0
Moisés da Silveira, Jefferson Luiz; Xavier, Eduardo Candido; Miyazawa, Flávio Keidi. A note on a two dimensional knapsack problem with unloading constraints. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 47 (2013) no. 4, pp. 315-324. doi: 10.1051/ita/2013037
Cité par Sources :