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 , and items of different classes, each item with class and size . 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 . 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 bins, such that, the total size of all items and shelf divisors packed in any bin is at most for a given and 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 different classes.
Mots-clés : bin packing, approximation algorithms
@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}, pages = {239--248}, publisher = {EDP-Sciences}, volume = {43}, number = {2}, year = {2009}, doi = {10.1051/ita:2008027}, mrnumber = {2512257}, zbl = {1166.68368}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ita:2008027/} }
TY - JOUR AU - Xavier, Eduardo C. AU - Miyazawa, Flàvio Keidi TI - A note on dual approximation algorithms for class constrained bin packing problems JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2009 SP - 239 EP - 248 VL - 43 IS - 2 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ita:2008027/ DO - 10.1051/ita:2008027 LA - en ID - ITA_2009__43_2_239_0 ER -
%0 Journal Article %A Xavier, Eduardo C. %A Miyazawa, Flàvio Keidi %T A note on dual approximation algorithms for class constrained bin packing problems %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2009 %P 239-248 %V 43 %N 2 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ita:2008027/ %R 10.1051/ita:2008027 %G en %F 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) no. 2, pp. 239-248. doi : 10.1051/ita:2008027. http://archive.numdam.org/articles/10.1051/ita:2008027/
[1] 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
, and ,[2] A two-phase roll cutting problem. Eur. J. Oper. Res. 44 (1990) 185-196. | Zbl
, and ,[3] Design and implementation of scalable continous media servers. Parallel Comput. 24 (1998) 91-122. | Zbl
and ,[4] Approximation algorithms for data placement on parallel disks, in Proceedings of SODA (2000) 223-232. | MR | Zbl
, , , and ,[5] Using dual approximation algorithms for schedulling problems: practical and theoretical results. J. ACM 34 (1987) 144-162. | MR
and ,[6] The one dimensional compartmentalized cutting stock problem: a case study. Eur. J. Oper. Res. 183 (2007) 1183-1195. | MR | Zbl
, and ,[7] The surplus inventory matching problem in the process industry. Oper. Res. 48 (2000) 505-516.
, , and ,[8] Algorithms for non-uniform size data placement on parallel disks. J. Algorithms 60 (2006) 144-167. | MR | Zbl
and ,[9] The constrained compartmentalized knapsack problem. Comput. Oper. Res. 34 (2007) 2109-2129. | MR | Zbl
and ,[10] The co-printing problem: A packing problem with a color constraint. Oper. Res. 52 (2004) 623-638. | MR | Zbl
and ,[11] On two class-constrained versions of the multiple knapsack problem. Algorithmica 29 (2001) 442-467. | MR | Zbl
and ,[12] Polynomial time approximation schemes for class-constrained packing problems. J. Scheduling 4 (2001) 313-338. | MR | Zbl
and ,[13] Multiprocessor scheduling with machine allotment and parallelism constraints. Algorithmica 32 (2002) 651-678. | MR | Zbl
and ,[14] 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
and ,[15] Tight bounds for online class-constrained packing. Theoret. Comput. Sci. 321 (2004) 103-123. | MR | Zbl
and ,[16] 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 | Zbl
,[17] Disk load balancing for video-on-demand-systems. Multimedia Syst. 5 (1997) 358-370.
, and ,[18] Approximation schemes for knapsack problems with shelf divisions. Theoret. Comput. Sci. 352 (2006) 71-84. | MR | Zbl
and ,[19] The class constrained bin packing problem with applications to video-on-demand. Theoret. Comput. Sci. 393 (2008) 240-259. | MR | Zbl
and ,[20] A one-dimensional bin packing problem with shelf divisions. Discrete Appl. Math. 156 (2008) 1083-1096. | MR | Zbl
and ,Cité par Sources :