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

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 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 + ε 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 - 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 \}&gt;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 }&gt;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. [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. [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. [3] S. Ghandeharizadeh and R.R. Muntz, Design and implementation of scalable continous media servers. Parallel Comput. 24 (1998) 91–122. Zbl0896.68009
  4. [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. [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. [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. [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. [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. [9] F.P. Marques and M. Arenales, The constrained compartmentalized knapsack problem. Comput. Oper. Res. 34 (2007) 2109–2129. Zbl1112.90073MR2273812
  10. [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. [11] H. Shachnai and T. Tamir, On two class-constrained versions of the multiple knapsack problem. Algorithmica 29 (2001) 442–467. Zbl0969.68183MR1799270
  12. [12] H. Shachnai and T. Tamir, Polynomial time approximation schemes for class-constrained packing problems. J. Scheduling 4 (2001) 313–338. Zbl1028.90048MR2016465
  13. [13] H. Shachnai and T. Tamir, Multiprocessor scheduling with machine allotment and parallelism constraints. Algorithmica 32 (2002) 651–678. Zbl1009.68014MR1875575
  14. [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. [15] H. Shachnai and T. Tamir, Tight bounds for online class-constrained packing. Theoret. Comput. Sci. 321 (2004) 103–123. Zbl1067.90144MR2069325
  16. [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. [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. [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. [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. [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 ?

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.