# A note on dual approximation algorithms for class constrained bin packing problems

Eduardo C. Xavier; Flàvio Keidi Miyazawa

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

- Volume: 43, Issue: 2, page 239-248
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topXavier, Eduardo C., and 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 43.2 (2009): 239-248. <http://eudml.org/doc/245985>.

@article{Xavier2009,

abstract = {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+\{\varepsilon \}$ for a given $\{\varepsilon \}>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.},

author = {Xavier, Eduardo C., Miyazawa, Flàvio Keidi},

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

keywords = {bin packing; approximation algorithms},

language = {eng},

number = {2},

pages = {239-248},

publisher = {EDP-Sciences},

title = {A note on dual approximation algorithms for class constrained bin packing problems},

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

volume = {43},

year = {2009},

}

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

PB - EDP-Sciences

VL - 43

IS - 2

SP - 239

EP - 248

AB - 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+{\varepsilon }$ for a given ${\varepsilon }>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.

LA - eng

KW - bin packing; approximation algorithms

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

ER -

## References

top- [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). Zbl0984.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. Zbl0684.90048
- [3] S. Ghandeharizadeh and R.R. Muntz, Design and implementation of scalable continous media servers. Parallel Comput. 24 (1998) 91–122. Zbl0896.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. Zbl0961.68010MR1754860
- [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. MR882666
- [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. Zbl1138.90457MR2343746
- [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. Zbl1112.68138MR2237286
- [9] F.P. Marques and M. Arenales, The constrained compartmentalized knapsack problem. Comput. Oper. Res. 34 (2007) 2109–2129. Zbl1112.90073MR2273812
- [10] M. Peeters and Z. Degraeve, The co-printing problem: A packing problem with a color constraint. Oper. Res. 52 (2004) 623–638. Zbl1165.90335MR2075797
- [11] H. Shachnai and T. Tamir, On two class-constrained versions of the multiple knapsack problem. Algorithmica 29 (2001) 442–467. Zbl0969.68183MR1799270
- [12] H. Shachnai and T. Tamir, Polynomial time approximation schemes for class-constrained packing problems. J. Scheduling 4 (2001) 313–338. Zbl1028.90048MR2016465
- [13] H. Shachnai and T. Tamir, Multiprocessor scheduling with machine allotment and parallelism constraints. Algorithmica 32 (2002) 651–678. Zbl1009.68014MR1875575
- [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. Zbl1279.68361MR2080790
- [15] H. Shachnai and T. Tamir, Tight bounds for online class-constrained packing. Theoret. Comput. Sci. 321 (2004) 103–123. Zbl1067.90144MR2069325
- [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. Zbl1034.90014MR1764686
- [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. Zbl1090.90168MR2207509
- [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. Zbl1135.68636MR2397256
- [20] E.C. Xavier and F.K. Miyazawa, A one-dimensional bin packing problem with shelf divisions. Discrete Appl. Math. 156 (2008) 1083–1096. Zbl1138.68067MR2404222

## NotesEmbed ?

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