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

Eduardo C. Xavier; Flàvio Keidi Miyazawa

RAIRO - Theoretical Informatics and Applications (2008)

- 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 43.2 (2008): 239-248. <http://eudml.org/doc/92914>.

@article{Xavier2008,

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 ce and size
se. 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.
},

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

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Bin packing; approximation algorithms.; bin packing; approximation algorithms},

language = {eng},

month = {10},

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/92914},

volume = {43},

year = {2008},

}

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

DA - 2008/10//

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 ce and size
se. 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.

LA - eng

KW - Bin packing; approximation algorithms.; bin packing; approximation algorithms

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

ER -

## References

top- 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 Mathematics7 (2001). Zbl0984.90058
- 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
- S. Ghandeharizadeh and R.R. Muntz, Design and implementation of scalable continous media servers. Parallel Comput.24 (1998) 91–122. Zbl0896.68009
- 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.68010
- D.S. Hochbaum and D.B. Shmoys, Using dual approximation algorithms for schedulling problems: practical and theoretical results. J. ACM34 (1987) 144–162.
- 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.90457
- 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.
- S.R. Kashyap and S. Khuller, Algorithms for non-uniform size data placement on parallel disks. J. Algorithms60 (2006) 144–167. Zbl1112.68138
- F.P. Marques and M. Arenales, The constrained compartmentalized knapsack problem. Comput. Oper. Res.34 (2007) 2109–2129. Zbl1112.90073
- M. Peeters and Z. Degraeve, The co-printing problem: A packing problem with a color constraint. Oper. Res.52 (2004) 623–638. Zbl1165.90335
- H. Shachnai and T. Tamir, On two class-constrained versions of the multiple knapsack problem. Algorithmica29 (2001) 442–467. Zbl0969.68183
- H. Shachnai and T. Tamir, Polynomial time approximation schemes for class-constrained packing problems. J. Scheduling4 (2001) 313–338. Zbl1028.90048
- H. Shachnai and T. Tamir, Multiprocessor scheduling with machine allotment and parallelism constraints. Algorithmica32 (2002) 651–678. Zbl1009.68014
- 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.68361
- H. Shachnai and T. Tamir, Tight bounds for online class-constrained packing. Theoret. Comput. Sci.321 (2004) 103–123. Zbl1067.90144
- 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.90014
- J.L. Wolf, P.S. Wu and H. Shachnai, Disk load balancing for video-on-demand-systems. Multimedia Syst.5 (1997) 358–370.
- E.C. Xavier and F.K. Miyazawa, Approximation schemes for knapsack problems with shelf divisions. Theoret. Comput. Sci.352 (2006) 71–84. Zbl1090.90168
- 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.68636
- E.C. Xavier and F.K. Miyazawa, A one-dimensional bin packing problem with shelf divisions. Discrete Appl. Math.156 (2008) 1083–1096. Zbl1138.68067

## NotesEmbed ?

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