The class constrained bin packing problem with applications to video-on-demand

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 size B with C compartments, and n items of Q different classes, each item i∈{1,…,n} with class ci and size si. The problem is to pack the items into bins, where each bin contains at most C different classes and has total items size at most B. We present several approximation algorithms for offline and online versions of the problem.