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.

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.

DOI : 10.1051/ita/2013037
Classification : 68W25, 05B40, 90C27
Mots-clés : knapsack problem, approximation algorithms, unloading/loading constraints 
@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://www.numdam.org/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://www.numdam.org/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://www.numdam.org/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. http://www.numdam.org/articles/10.1051/ita/2013037/

[1] A. Caprara and M. Monaci, On the two-dimensional knapsack problem. Oper. Res. Lett. 32 (2004) 5-14. | Zbl

[2] E.G. Coffman Jr., M.R. Garey, D.S. Johnson and R.E. Tarjan, Performance bounds for level-oriented two dimensional packing algorithms. SIAM J. Comput. 9 (1980) 808-826. | MR | Zbl

[3] J.L.S. Da Silveira, E.C. Xavier and F.K. Miyazawa, 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

[4] J.L.M. Da Silveira, F.K. Miyazawa and E.C. Xavier, Heuristics for the strip packing problem with unloading constraints. Comput. Oper. Res. 40 (2013) 991-1003. | MR

[5] B.L.P. De Azevedo, P.H. Hokama, F.K. Miyazawa and E.C. Xavier, 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] M. Gendreau, M. Iori, G. Laporte and S. Martello, A tabu search heuristic for the vehicle routing problem with two-dimensional loading constraints. Networks 51 (2007) 4-18. | MR | Zbl

[7] R. Harren, Approximating the orthogonal knapsack problem for hypercubesi in ICALP (1), vol. 4051 of Lect. Notes Comput. Sci. (2006) 238-249. | MR | Zbl

[8] R. Harren and R. Van Stee, Absolute approximation ratios for packing rectangles into bins. J. Sched. (2010). | MR | Zbl

[9] O.H. Ibarra and C.E. Kim, Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM 22 (1975) 463-468. | MR | Zbl

[10] M. Iori, 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] K. Jansen and L. Prädel, How to maximize the total area of rectangles packed into a rectangle. Technical Report 0908. Christian-Albrechts-Universität zu kiel, Italy (2009).

[12] K. Jansen and R. Solis-Oba, 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 | Zbl

[13] K. Jansen and G. Zhang, 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

[14] L. Junqueira, R. Morabito and D. Yamashita, Abordagens para problemas de carregamento de contêiners com considerações de múltiplos destinos. Gestão & Produção. 18 (2011).

[15] L. Junqueira, R. Morabito and D.S. Yamashita, Mip-based approaches for the container loading problem with multi-drop constraints. Ann. Oper. Res. 199 (2012) 51-75. | MR | Zbl

[16] E.E. Zachariadis, C.T. Kiranoudis and C.D. Tarantilis, A guided tabu search for the vehicle routing problem with two-dimensional loading constraints. Eur. J. Oper. Res. 195 (2009) 729-743. | Zbl

Cité par Sources :