@techreport{TR-IC-05-16,
  number = {IC-05-16},
  author = {E. C. Xavier and F. K. Miyazawa},
  title = {On-line Class Constraint Bin Packing},
  month = {July},
  year = {2005}, 
  institution = {Institute of Computing, University of Campinas},
  note = {In English, 9 pages.
    \par\selectlanguage{english}\textbf{Abstract}
       In this paper we present approximation results for the on-line
       class constrained bin packing problem.  In this problem we are
       given bins of capacity $1$ with $C$ compartments, and $n$ items
       of $Q$ different classes, each item $i \in \{1,\ldots,n\}$ with
       class $c(i)$ and size $s(i)$. The problem consists to pack the
       items into bins in an on-line way, where each bin contains at
       most $C$ different classes and has total items size at most
       $1$.  We show that the bounded space version of this problem
       does not have an algorithm with constant competitive ratio. If
       each item have size at least $eps <1$, we show that the
       problem does not admit an algorithm with competitive ratio
       better than $O(1/C\; eps)$. In the unbounded case we show that
       the First-Fit algorithm has competitive ratio in $[2.7 , 3]$
       and we present an algorithm with competitive ratio in $[2.66 ,
       2.75]$.
  }
}