# A note on a two dimensional knapsack problem with unloading constraints

Jefferson Luiz Moisés da Silveira; Eduardo Candido Xavier; Flávio Keidi Miyazawa

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2013)

- Volume: 47, Issue: 4, page 315-324
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topMoisés da Silveira, Jefferson Luiz, Xavier, Eduardo Candido, and 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 47.4 (2013): 315-324. <http://eudml.org/doc/273036>.

@article{MoisésdaSilveira2013,

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 + ϵ)-approximation algorithm when the bin is a square. We also present (3 + ϵ)-approximation algorithms for two special cases of this problem.},

author = {Moisés da Silveira, Jefferson Luiz, Xavier, Eduardo Candido, Miyazawa, Flávio Keidi},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {knapsack problem; approximation algorithms; unloading/loading constraints},

language = {eng},

number = {4},

pages = {315-324},

publisher = {EDP-Sciences},

title = {A note on a two dimensional knapsack problem with unloading constraints},

url = {http://eudml.org/doc/273036},

volume = {47},

year = {2013},

}

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

PB - EDP-Sciences

VL - 47

IS - 4

SP - 315

EP - 324

AB - 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.

LA - eng

KW - knapsack problem; approximation algorithms; unloading/loading constraints

UR - http://eudml.org/doc/273036

ER -

## References

top- [1] A. Caprara and M. Monaci, On the two-dimensional knapsack problem. Oper. Res. Lett.32 (2004) 5–14. Zbl1056.90115
- [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. Zbl0447.68079MR592769
- [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. Zbl1268.90074
- [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. MR3017799
- [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. Networks51 (2007) 4–18. Zbl1146.90012MR2375146
- [7] R. Harren, Approximating the orthogonal knapsack problem for hypercubesi in ICALP (1), vol. 4051 of Lect. Notes Comput. Sci. (2006) 238–249. Zbl1223.90052MR2305530
- [8] R. Harren and R. van Stee, Absolute approximation ratios for packing rectangles into bins. J. Sched. (2010). Zbl1280.68295MR2896971
- [9] O.H. Ibarra and C.E. Kim, Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM22 (1975) 463–468. Zbl0345.90049MR378463
- [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. Zbl1143.90399MR2481714
- [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. Zbl1317.68280MR2291055
- [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. Zbl1251.90324MR2971805
- [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. Zbl1155.90331

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.