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

Abstract

top
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.

How to cite

top

Xavier, 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
  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 Mathematics7 (2001).  
  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.  
  3. S. Ghandeharizadeh and R.R. Muntz, Design and implementation of scalable continous media servers. Parallel Comput.24 (1998) 91–122.  
  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.  
  5. D.S. Hochbaum and D.B. Shmoys, Using dual approximation algorithms for schedulling problems: practical and theoretical results. J. ACM34 (1987) 144–162.  
  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.  
  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. Algorithms60 (2006) 144–167.  
  9. F.P. Marques and M. Arenales, The constrained compartmentalized knapsack problem. Comput. Oper. Res.34 (2007) 2109–2129.  
  10. M. Peeters and Z. Degraeve, The co-printing problem: A packing problem with a color constraint. Oper. Res.52 (2004) 623–638.  
  11. H. Shachnai and T. Tamir, On two class-constrained versions of the multiple knapsack problem. Algorithmica29 (2001) 442–467.  
  12. H. Shachnai and T. Tamir, Polynomial time approximation schemes for class-constrained packing problems. J. Scheduling4 (2001) 313–338.  
  13. H. Shachnai and T. Tamir, Multiprocessor scheduling with machine allotment and parallelism constraints. Algorithmica32 (2002) 651–678.  
  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.  
  15. H. Shachnai and T. Tamir, Tight bounds for online class-constrained packing. Theoret. Comput. Sci.321 (2004) 103–123.  
  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.  
  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.  
  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.  
  20. E.C. Xavier and F.K. Miyazawa, A one-dimensional bin packing problem with shelf divisions. Discrete Appl. Math.156 (2008) 1083–1096.  

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.