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.

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+\epsilon$ for a given $\epsilon >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.

DOI : https://doi.org/10.1051/ita:2008027
Classification : 68W25
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},
zbl = {1166.68368},
mrnumber = {2512257},
language = {en},
url = {http://www.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
DA  - 2009///
SP  - 239
EP  - 248
VL  - 43
IS  - 2
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2008027/
UR  - https://zbmath.org/?q=an%3A1166.68368
UR  - https://www.ams.org/mathscinet-getitem?mr=2512257
UR  - https://doi.org/10.1051/ita:2008027
DO  - 10.1051/ita:2008027
LA  - en
ID  - ITA_2009__43_2_239_0
ER  - 
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://www.numdam.org/articles/10.1051/ita:2008027/`

[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

Cité par Sources :