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},
volume = {47},
year = {2013},
pages = {315-324},
doi = {10.1051/ita/2013037},
mrnumber = {3132294},
language = {en},
url = {http://dml.mathdoc.fr/item/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) pp. 315-324. doi : 10.1051/ita/2013037. http://gdmltest.u-ga.fr/item/ITA_2013__47_4_315_0/
[1] and , On the two-dimensional knapsack problem. Oper. Res. Lett. 32 (2004) 5-14. | Zbl 1056.90115
[2] , , and , Performance bounds for level-oriented two dimensional packing algorithms. SIAM J. Comput. 9 (1980) 808-826. | MR 592769 | Zbl 0447.68079
[3] , and , Two dimensional knapsack with unloading constraints, in VI Latin American Algorithms, Graphs and Optimization Symposium (LAGOS 2011), Electronic Notes in Discrete Math. (2011) 1-4. | Zbl 1268.90074
[4] , and , Heuristics for the strip packing problem with unloading constraints. Comput. Oper. Res. 40 (2013) 991-1003. | MR 3017799
[5] , , and , A branch-and-cut approach for the vehicle routing problem with two-dimensional loading constraints, in Simpósio Brasileiro de Pesquisa Operacional - SBPO, Porto Seguro, Brazil (2009).
[6] , , and , A tabu search heuristic for the vehicle routing problem with two-dimensional loading constraints. Networks 51 (2007) 4-18. | MR 2375146 | Zbl 1146.90012
[7] , Approximating the orthogonal knapsack problem for hypercubesi in ICALP (1), vol. 4051 of Lect. Notes Comput. Sci. (2006) 238-249. | MR 2305530 | Zbl 1223.90052
[8] and , Absolute approximation ratios for packing rectangles into bins. J. Sched. (2010). | MR 2896971 | Zbl 1280.68295
[9] and , Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM 22 (1975) 463-468. | MR 378463 | Zbl 0345.90049
[10] , J-J. S-González and D. Vigo, An exact approach for the vehicle routing problem with two-dimensional loading constraints. Transport. Sci. 41 (2007) 253-264.
[11] and , How to maximize the total area of rectangles packed into a rectangle. Technical Report 0908. Christian-Albrechts-Universität zu kiel, Italy (2009).
[12] and , A polynomial time approximation scheme for the square packing problem, in Proc. of the Integer Programming and Combinatorial Optimization, vol. 5035, in Lect. Note Comput. Sci. Springer Berlin, Heidelberg (2008) 184-198. | MR 2481714 | Zbl 1143.90399
[13] and , On rectangle packing: maximizing benefits, in Proc. of the 15th ACM-SIAM Symposium on Discrete Algorithms. Society for Industial and Applied Mathematics, Philadephia, PA, USA (2004) 204-213. | MR 2291055
[14] , and , Abordagens para problemas de carregamento de contêiners com considerações de múltiplos destinos. Gestão & Produção. 18 (2011).
[15] , and , Mip-based approaches for the container loading problem with multi-drop constraints. Ann. Oper. Res. 199 (2012) 51-75. | MR 2971805 | Zbl 1251.90324
[16] , and , A guided tabu search for the vehicle routing problem with two-dimensional loading constraints. Eur. J. Oper. Res. 195 (2009) 729-743. | Zbl 1155.90331