The Class Constrained Bin Packing Problem With Applications To Video-on-demand

dc.creatorXavier E.C.
dc.creatorMiyazawa F.K.
dc.date2006
dc.date2015-06-30T18:12:50Z
dc.date2015-11-26T14:27:38Z
dc.date2015-06-30T18:12:50Z
dc.date2015-11-26T14:27:38Z
dc.date.accessioned2018-03-28T21:30:47Z
dc.date.available2018-03-28T21:30:47Z
dc.identifier3540369252; 9783540369257
dc.identifierLecture Notes In Computer Science (including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics). , v. 4112 LNCS, n. , p. 439 - 448, 2006.
dc.identifier3029743
dc.identifier
dc.identifierhttp://www.scopus.com/inward/record.url?eid=2-s2.0-33749563378&partnerID=40&md5=05a2888dfafb7ac86b1b9a2a22c8518d
dc.identifierhttp://www.repositorio.unicamp.br/handle/REPOSIP/103521
dc.identifierhttp://repositorio.unicamp.br/jspui/handle/REPOSIP/103521
dc.identifier2-s2.0-33749563378
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1246388
dc.descriptionIn 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.
dc.description4112 LNCS
dc.description
dc.description439
dc.description448
dc.descriptionCoffman 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
dc.descriptionDawande, M., Kalagnanam, J., Sethuraman, J., Variable sized bin packing with color constraints (1998) Technical Report, , IBM, T.J. Watson Research Center, NY
dc.descriptionDawande, M., Kalagnanam, J., Sethuraman, J., Variable sized bin packing with color constraints (2001) Electronic Notes in Dicrete Mathematics, 7. , Proceedings of Graco 2001
dc.descriptionDe La Vega, W.F., Lueker, G.S., Bin packing can be solved within 1 + ε in linear time (1981) Combinatorica, 1 (4), pp. 349-355
dc.descriptionGolubchik, L., Khanna, S., Khuller, S., Thurimella, R., Zhu, A., Approximation algorithms for data placement on parallel disks (2000) Proceedings of SODA, pp. 223-232
dc.descriptionJohnson, 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
dc.descriptionKashyap, 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
dc.descriptionShachnai, H., Tamir, T., On two class-constrained versions of the multiple knapsack problem (2001) Algorithmica, 29, pp. 442-467
dc.descriptionShachnai, H., Tamir, T., Polynomial time approximation schemes for class-constrained packing problems (2001) Journal of Scheduling, 4 (6), pp. 313-338
dc.descriptionShachnai, 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
dc.descriptionShachnai, H., Tamir, T., Tight bounds for online class-constrained packing (2004) Theoretical Computer Science, 321 (1), pp. 103-123
dc.languageen
dc.publisher
dc.relationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
dc.rightsfechado
dc.sourceScopus
dc.titleThe Class Constrained Bin Packing Problem With Applications To Video-on-demand
dc.typeActas de congresos


Este ítem pertenece a la siguiente institución