A note on dual approximation algorithms for class constrained bin packing problems
Xavier, Eduardo C. ; Miyazawa, Flàvio Keidi
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009), p. 239-248 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

In this paper we present a dual approximation scheme for the class constrained shelf bin packing problem. In this problem, we are given bins of capacity 1, and n items of Q different classes, each item e with class c e and size s e . The problem is to pack the items into bins, such that two items of different classes packed in a same bin must be in different shelves. Items in a same shelf are packed consecutively. Moreover, items in consecutive shelves must be separated by shelf divisors of size d. In a shelf bin packing problem, we have to obtain a shelf packing such that the total size of items and shelf divisors in any bin is at most 1. A dual approximation scheme must obtain a shelf packing of all items into N bins, such that, the total size of all items and shelf divisors packed in any bin is at most 1+ε for a given ε>0 and N is the number of bins used in an optimum shelf bin packing problem. Shelf divisors are used to avoid contact between items of different classes and can hold a set of items until a maximum given weight. We also present a dual approximation scheme for the class constrained bin packing problem. In this problem, there is no use of shelf divisors, but each bin uses at most C different classes.

Publié le : 2009-01-01
DOI : https://doi.org/10.1051/ita:2008027
Classification:  68W25 
@article{ITA_2009__43_2_239_0,
     author = {Xavier, Eduardo C. and Miyazawa, Fl\`avio Keidi},
     title = {A note on dual approximation algorithms for class constrained bin packing problems},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {43},
     year = {2009},
     pages = {239-248},
     doi = {10.1051/ita:2008027},
     mrnumber = {2512257},
     zbl = {1166.68368},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2009__43_2_239_0}
}

Xavier, Eduardo C.; Miyazawa, Flàvio Keidi. A note on dual approximation algorithms for class constrained bin packing problems. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009) pp. 239-248. doi : 10.1051/ita:2008027. http://gdmltest.u-ga.fr/item/ITA_2009__43_2_239_0/

[1] M. Dawande, J. Kalagnanam and J. Sethuranam, Variable sized bin packing with color constraints, in Proceedings of the 1th Brazilian Symposium on Graph Algorithms and Combinatorics. Electronic Notes in Discrete Mathematics 7 (2001). | Zbl 0984.90058

[2] J.S. Ferreira, M.A. Neves and P. Fonseca E Castro, A two-phase roll cutting problem. Eur. J. Oper. Res. 44 (1990) 185-196. | Zbl 0684.90048

[3] S. Ghandeharizadeh and R.R. Muntz, Design and implementation of scalable continous media servers. Parallel Comput. 24 (1998) 91-122. | Zbl 0896.68009

[4] L. Golubchik, S. Khanna, S. Khuller, R. Thurimella and A. Zhu, Approximation algorithms for data placement on parallel disks, in Proceedings of SODA (2000) 223-232. | MR 1754860 | Zbl 0961.68010

[5] D.S. Hochbaum and D.B. Shmoys, Using dual approximation algorithms for schedulling problems: practical and theoretical results. J. ACM 34 (1987) 144-162. | MR 882666

[6] R. Hoto, M. Arenales and N. Maculan, The one dimensional compartmentalized cutting stock problem: a case study. Eur. J. Oper. Res. 183 (2007) 1183-1195. | MR 2343746 | Zbl 1138.90457

[7] J.R. Kalagnanam, M.W. Dawande, M. Trumbo and H.S. Lee, The surplus inventory matching problem in the process industry. Oper. Res. 48 (2000) 505-516.

[8] S.R. Kashyap and S. Khuller, Algorithms for non-uniform size data placement on parallel disks. J. Algorithms 60 (2006) 144-167. | MR 2237286 | Zbl 1112.68138

[9] F.P. Marques and M. Arenales, The constrained compartmentalized knapsack problem. Comput. Oper. Res. 34 (2007) 2109-2129. | MR 2273812 | Zbl 1112.90073

[10] M. Peeters and Z. Degraeve, The co-printing problem: A packing problem with a color constraint. Oper. Res. 52 (2004) 623-638. | MR 2075797 | Zbl 1165.90335

[11] H. Shachnai and T. Tamir, On two class-constrained versions of the multiple knapsack problem. Algorithmica 29 (2001) 442-467. | MR 1799270 | Zbl 0969.68183

[12] H. Shachnai and T. Tamir, Polynomial time approximation schemes for class-constrained packing problems. J. Scheduling 4 (2001) 313-338. | MR 2016465 | Zbl 1028.90048

[13] H. Shachnai and T. Tamir, Multiprocessor scheduling with machine allotment and parallelism constraints. Algorithmica 32 (2002) 651-678. | MR 1875575 | Zbl 1009.68014

[14] H. Shachnai and T. Tamir, Approximation schemes for generalized 2-dimensional vector packing with application to data placement, in Proceedings of 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, RANDOM-APPROX. Lect. Notes Comput. Sci. 2764 (2003) 165-177. | MR 2080790

[15] H. Shachnai and T. Tamir, Tight bounds for online class-constrained packing. Theoret. Comput. Sci. 321 (2004) 103-123. | MR 2069325 | Zbl 1067.90144

[16] G.J. Woeginger, When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (fptas)? INFORMS J. Comput. 12 (2000) 57-74. | MR 1764686 | Zbl 1034.90014

[17] J.L. Wolf, P.S. Wu and H. Shachnai, Disk load balancing for video-on-demand-systems. Multimedia Syst. 5 (1997) 358-370.

[18] E.C. Xavier and F.K. Miyazawa, Approximation schemes for knapsack problems with shelf divisions. Theoret. Comput. Sci. 352 (2006) 71-84. | MR 2207509 | Zbl 1090.90168

[19] E.C. Xavier and F.K. Miyazawa, The class constrained bin packing problem with applications to video-on-demand. Theoret. Comput. Sci. 393 (2008) 240-259. | MR 2397256 | Zbl 1135.68636

[20] E.C. Xavier and F.K. Miyazawa, A one-dimensional bin packing problem with shelf divisions. Discrete Appl. Math. 156 (2008) 1083-1096. | MR 2404222 | Zbl 1138.68067