  Following the work of Anily et al., we consider a variant of bin packing,
called "bin packing with general cost structures" (GCBP) and design an
asymptotic fully polynomial time approximation scheme (AFPTAS) for this
problem. In the classic bin packing problem, a set of one-dimensional items is
to be assigned to subsets of total size at most 1, that is, to be packed into
unit sized bins. However, in GCBP, the cost of a bin is not 1 as in classic bin
packing, but it is a non-decreasing and concave function of the number of items
packed in it, where the cost of an empty bin is zero. The construction of the
AFPTAS requires novel techniques for dealing with small items, which are
developed in this work. In addition, we develop a fast approximation algorithm
which acts identically for all non-decreasing and concave functions, and has an
asymptotic approximation ratio of 1.5 for all functions simultaneously.
