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
topAbstract
topHow 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).
- 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.
- S. Ghandeharizadeh and R.R. Muntz, Design and implementation of scalable continous media servers. Parallel Comput.24 (1998) 91–122.
- 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.
- 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.
- 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.
- F.P. Marques and M. Arenales, The constrained compartmentalized knapsack problem. Comput. Oper. Res.34 (2007) 2109–2129.
- M. Peeters and Z. Degraeve, The co-printing problem: A packing problem with a color constraint. Oper. Res.52 (2004) 623–638.
- H. Shachnai and T. Tamir, On two class-constrained versions of the multiple knapsack problem. Algorithmica29 (2001) 442–467.
- H. Shachnai and T. Tamir, Polynomial time approximation schemes for class-constrained packing problems. J. Scheduling4 (2001) 313–338.
- H. Shachnai and T. Tamir, Multiprocessor scheduling with machine allotment and parallelism constraints. Algorithmica32 (2002) 651–678.
- 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.
- H. Shachnai and T. Tamir, Tight bounds for online class-constrained packing. Theoret. Comput. Sci.321 (2004) 103–123.
- 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.
- 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.
- 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.
- E.C. Xavier and F.K. Miyazawa, A one-dimensional bin packing problem with shelf divisions. Discrete Appl. Math.156 (2008) 1083–1096.
NotesEmbed ?
topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.