Actas de congresos
The Class Constrained Bin Packing Problem With Applications To Video-on-demand
Registro en:
3540369252; 9783540369257
Lecture Notes In Computer Science (including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics). , v. 4112 LNCS, n. , p. 439 - 448, 2006.
3029743
2-s2.0-33749563378
Autor
Xavier E.C.
Miyazawa F.K.
Institución
Resumen
In this paper we present approximation results for the class constrained bin packing problem that has applications to Video-on-Demand Systems. In this problem we are given bins of capacity B with C compartments, and n items of Q different classes. The problem is to pack the items into the minimum number of bins, where each bin contains items of at most C different classes and has total items size at most B. We present several approximation algorithms for off-line and online versions of the problem. © Springer-Verlag Berlin Heidelberg 2006. 4112 LNCS
439 448 Coffman Jr., E.G., Garey, M.R., Johnson, D.S., Approximation algorithms for bin packing: A survey (1997) Approximation Algorithms for NP-hard Problems, pp. 46-93. , D. Hochbaum, editor, chapter 2. PWS Dawande, M., Kalagnanam, J., Sethuraman, J., Variable sized bin packing with color constraints (1998) Technical Report, , IBM, T.J. Watson Research Center, NY Dawande, M., Kalagnanam, J., Sethuraman, J., Variable sized bin packing with color constraints (2001) Electronic Notes in Dicrete Mathematics, 7. , Proceedings of Graco 2001 De La Vega, W.F., Lueker, G.S., Bin packing can be solved within 1 + ε in linear time (1981) Combinatorica, 1 (4), pp. 349-355 Golubchik, L., Khanna, S., Khuller, S., Thurimella, R., Zhu, A., Approximation algorithms for data placement on parallel disks (2000) Proceedings of SODA, pp. 223-232 Johnson, D.S., Demers, A., Ullman, J.D., Garey, M.R., Graham, R.L., Worst-case performance bounds for simple one-dimensional packing algorithms (1974) SIAM Journal on Computing, 3, pp. 299-325 Kashyap, S.R., Khuller, S., Algorithms for non-uniform size data placement on parallel disks (2003) Lecture Notes in Computer Science, 2914, pp. 265-276. , Proceedings of FSTTCS Shachnai, H., Tamir, T., On two class-constrained versions of the multiple knapsack problem (2001) Algorithmica, 29, pp. 442-467 Shachnai, H., Tamir, T., Polynomial time approximation schemes for class-constrained packing problems (2001) Journal of Scheduling, 4 (6), pp. 313-338 Shachnai, H., Tamir, T., Approximation schemes for generalized 2-dimensional vector packing with application to data placement (2003) Lecture Notes in Computer Science, 2764, pp. 165-177. , Proceedings of 6th RANDOM-APPROX Shachnai, H., Tamir, T., Tight bounds for online class-constrained packing (2004) Theoretical Computer Science, 321 (1), pp. 103-123